SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
prop_obbt.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file prop_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"
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"
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 */
133
134/** bound data */
135struct 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};
147typedef struct Bound BOUND;
148
149/* all possible corners of a rectangular domain */
158typedef enum Corner CORNER;
159
160/** bilinear bound data */
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};
168typedef struct BilinBound BILINBOUND;
169
170/** propagator data */
171struct 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 */
239static
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{
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
259
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
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 */
311static
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;
320
321 int nvars;
322 int i;
323
324 assert(scip != NULL);
326 assert(propdata != NULL);
327 assert(propdata->cutoffrow == NULL);
328
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 */
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");
344
345 for( i = 0; i < nvars; i++ )
346 {
348 }
350
351 /* add row to the LP */
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 */
361static
363 SCIP* scip, /**< SCIP data structure */
364 SCIP_VAR* var /**< variable to check */
365 )
366{
368}
369
370/** sets objective to minimize or maximize a single variable */
371static
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 {
394 }
395 else
396 {
397 SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, -coef) );
398 }
399
400#ifdef SCIP_DEBUG
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 */
418static
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;
431
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 ) */
445static
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);
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 {
466 itsleft = MAX(itsleft, 0);
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 */
475static
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
492
493 /* this function should not be called for fixed variables */
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 */
549static
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);
562
563 *found = FALSE;
564
565 /* make sure we are in probing mode having an optimal LP solution */
567
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 */
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 */
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 */
599
600 /* count nonzero coefficients in genvbound */
601 ncoefs = 0;
602 for( k = 0; k < nvars; k++ )
603 {
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 {
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 */
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 */
640
641 /* there should be no coefficient for x_i */
643
644 /* allocate memory for storing the genvbounds right-hand side variables and coefficients */
647
648 /* set c = lb*mu - ub*nu - z*gamma + l*alpha - u*beta */
650
651 /* subtract ( - z * gamma ) from c */
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
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)) ) ||
674 {
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 )
703
704 SCIPdebugMsg(scip, "LVB activity = %g lpobj = %g\n", activity, SCIPgetLPObjval(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 */
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",
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 */
735static
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;
748
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 */
758static
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);
771
772 switch( corner )
773 {
774 case LEFTBOTTOM:
777 break;
778 case RIGHTBOTTOM:
781 break;
782 case LEFTTOP:
785 break;
786 case RIGHTTOP:
789 break;
790 case FILTERED:
791 SCIPABORT();
792 }
793}
794
795/** helper function to return the two end points of a diagonal */
796static
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 */
838static
840 BILINBOUND* bilinbound /**< bilinear bound */
841 )
842{
843 assert(bilinbound->expr != NULL);
845
847}
848
849/** returns the second variable of a bilinear bound */
850static
852 BILINBOUND* bilinbound /**< bilinear bound */
853 )
854{
855 assert(bilinbound->expr != NULL);
857
859}
860
861/** returns the negative locks of the expression in a bilinear bound */
862static
864 BILINBOUND* bilinbound /**< bilinear bound */
865 )
866{
867 assert(bilinbound->expr != NULL);
868
870}
871
872/** returns the positive locks of the expression in a bilinear bound */
873static
875 BILINBOUND* bilinbound /**< bilinear bound */
876 )
877{
878 assert(bilinbound->expr != NULL);
879
881}
882
883/** computes the score of a bilinear term bound */
884static
886 SCIP* scip, /**< SCIP data structure */
887 SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
888 BILINBOUND* bilinbound /**< bilinear bound */
889 )
890{
893 SCIP_Real lbx = SCIPvarGetLbLocal(x);
894 SCIP_Real ubx = SCIPvarGetUbLocal(x);
895 SCIP_Real lby = SCIPvarGetLbLocal(y);
896 SCIP_Real uby = SCIPvarGetUbLocal(y);
897 SCIP_Real score;
898
899 assert(scip != NULL);
900 assert(randnumgen != NULL);
902
903 /* consider how often a bilinear term is present in the problem */
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 */
930static
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);
943
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 ?
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 {
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 */
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 */
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);
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 {
1049 BILINBOUND* bilinbound = propdata->bilinbounds[i];
1050 SCIP_Real solx;
1051 SCIP_Real soly;
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;)
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
1081
1084 bilinbound->filtered = bilinbound->filtered | corners[j]; /*lint !e641*/
1085 }
1086
1087#ifdef SCIP_DEBUG
1088 if( oldfiltered != bilinbound->filtered )
1089 {
1092 SCIPdebugMessage("filtered corners %d for (%s,%s) = (%g,%g) in [%g,%g]x[%g,%g]\n",
1095 }
1096#endif
1097 }
1098
1099 return SCIP_OKAY;
1100}
1101
1102/** enforces one round of filtering */
1103static
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);
1124 assert(propdata != NULL);
1125 assert(itlimit == -1 || itlimit >= 0);
1126 assert(nfiltered != NULL);
1127 assert(objcoefs != NULL);
1129 assert(nobjcoefs >= 0);
1130
1131 *nfiltered = 0;
1132
1133 /* get variable data */
1135
1136 /* solve LP */
1137 propdata->nfilterlpiters -= (int) SCIPgetNLPIterations(scip);
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 ?
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;
1174
1175 /* mark bound as filtered */
1176 bound->filtered = TRUE;
1177
1178 /* get the basis status of the variable */
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 {
1193
1194 filterbound = propdata->bounds[ objcoefsinds[j] ];
1196
1198 }
1199
1200#ifndef NDEBUG
1201 for( j = 0; j < nvars; ++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 {
1234
1235 filterbound = propdata->bounds[ objcoefsinds[j] ];
1237
1238 /* NOTE: only restore coefficients of nonfiltered bounds */
1239 if( !filterbound->filtered )
1240 {
1242 SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[ objcoefsinds[j] ]->var, objcoefs[j]) );
1243 }
1244 }
1245 }
1246
1247 /* get the corresponding variable's objective coefficient */
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 {
1255 }
1256 }
1257 }
1258
1259 return SCIP_OKAY;
1260}
1261
1262/** filter some bounds that are not improvable by solving auxiliary LPs */
1263static
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);
1284 assert(propdata != NULL);
1285 assert(itlimit == -1 || itlimit >= 0);
1286
1287 ntotalfiltered = 0;
1290
1291 /* get variable data */
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 {
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 */
1325 ++nobjcoefs;
1326 }
1327 }
1328 }
1329
1330 do
1331 {
1332 SCIPdebugMsg(scip, "doing a lower bounds round\n");
1334 ntotalfiltered += nfiltered;
1335 SCIPdebugMsg(scip, "filtered %d more bounds in lower bounds round\n", nfiltered);
1336
1337 /* update iterations left */
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);
1355 }
1356
1357 /* reset number of nontrivial objective coefficients */
1358 nobjcoefs = 0;
1359
1360#ifndef NDEBUG
1361 for( i = 0; i < nvars; ++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 */
1380 ++nobjcoefs;
1381 }
1382 }
1383 }
1384
1385 do
1386 {
1387 SCIPdebugMsg(scip, "doing an upper bounds round\n");
1389 SCIPdebugMsg(scip, "filtered %d more bounds in upper bounds round\n", nfiltered);
1390 ntotalfiltered += nfiltered;
1391 /* update iterations left */
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 */
1402
1403 return SCIP_OKAY;
1404}
1405
1406/** applies possible bound changes that were found */
1407static
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);
1421 assert(propdata != NULL);
1422 assert(result != NULL);
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 {
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) );
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 */
1474static
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);
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 */
1535static
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 */
1545static
1547{
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 */
1555static
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 */
1581static
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;
1594}
1595
1596/** evaluates a bound for the current LP solution */
1597static
1598SCIP_Real evalBound(
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) );
1610}
1611
1612/** returns the index of the next undone and unfiltered bound with the smallest distance */
1613static
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);
1626
1627 bestidx = -1;
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
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 */
1665static
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
1678 assert(success != NULL);
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 */
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 */
1708 assert(SCIPgetNCuts(scip) == 0);
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 {
1732 SCIPdebugMsg(scip, "apply separation - tightened=%u oldval=%e newval=%e\n", tightened, oldval,
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 */
1747static
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;
1758 SCIP_Longint itlimit;
1759 int nextboundidx;
1760
1761 assert(scip != NULL);
1762 assert(propdata != NULL);
1764
1765 /* update the number of left iterations */
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",
1830 SCIPdebugMsg(scip, "before solving var <%s>, LP value: %f\n",
1832
1833 SCIPdebugMsg(scip, "probing iterations before solve: %lld \n", SCIPgetNLPIterations(scip));
1834
1835 propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
1836
1837 /* now solve the LP */
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",
1848 SCIPdebugMsg(scip, "after solving var <%s>, LP value: %f\n",
1850
1851 /* update nleftiterations */
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 */
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),
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),
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);
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 */
1986static
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;
2020 continuenode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode;
2021 propdata->lastidx = -1;
2022 boundleft = FALSE;
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 */
2074
2075 /* start probing */
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 {
2114 }
2115
2116 /* set objective coefficients to zero */
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 */
2125 {
2127 }
2128 }
2129
2130 /* find new bounds for the variables */
2132
2133 if( nleftiterations > 0 || itlimit < 0 )
2134 {
2136 }
2137
2138 /* reset dual feastol and condition limit */
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
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
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 */
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
2208TERMINATE:
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 */
2240static
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);
2267
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)
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;
2292
2293 /* create new probing node to remove the added LP row afterwards */
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)) );
2302
2303 /* solve probing LP */
2304#ifdef NDEBUG
2305 {
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 */
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 */
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 {
2356 ++(*nnonzduals);
2357 }
2358 }
2359 }
2360 else
2361 {
2364 *constant = SCIP_INVALID;
2365 }
2366 }
2367
2368 /* release row and backtrack probing node */
2369 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2371
2372 /* reset objective function */
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 */
2388static
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;
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
2426
2429 SCIPdebugMsg(scip, "iteration limit: %lld\n", nleftiterations);
2430
2431 /* 1. start probing */
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 {
2441 }
2442
2443 /* 4. tighten LP feasibility tolerance to be at most feastol/10.0 */
2445
2446 /* we need to solve the probing LP before creating new probing nodes in solveBilinearLP() */
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 {
2460 int k;
2461
2462 bilinbound = propdata->bilinbounds[i];
2464
2465 SCIPdebugMsg(scip, "process %d: %s %s done=%u filtered=%d nunderest=%d noverest=%d\n", i,
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 {
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 */
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 */
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 */
2518 SCIPdebugMsg(scip, "LP iterations left: %lld\n", nleftiterations);
2519
2520 /* add inequality to quadratic constraint handler if it separates (xt,yt) */
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 */
2529 constant, &success) );
2530
2531 /* check whether the inequality has been accepted */
2532 if( success )
2533 {
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 */
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 */
2578
2579 return SCIP_OKAY;
2580}
2581
2582/** computes the score of a bound */
2583static
2584unsigned 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 {
2603 score += 1;
2604 break;
2606 score += 2;
2607 break;
2609 score += 3;
2610 break;
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 */
2626static
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
2642
2643 /* initialize nccounts to zero */
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 {
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 */
2685static
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);
2698}
2699
2700/** initializes interesting bounds */
2701static
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);
2720
2721 SCIPdebugMsg(scip, "initialize bounds\n");
2722
2723 /* get variable data */
2725
2726 /* count nonlinearities */
2728
2731
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]);
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]);
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 {
2793 SCIP_EXPR** exprs;
2794 int nexprs;
2795
2796 /* find nonlinear handler for bilinear terms */
2797 bilinnlhdlr = SCIPfindNlhdlrNonlinear(conshdlr, "bilinear");
2799
2800 /* collect all bilinear product in all nonlinear constraints */
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 {
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];
2834
2835 /* store and capture expression */
2836 bilinbound->expr = exprs[i];
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);
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 */
2893static
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 */
2902
2903 return SCIP_OKAY;
2904}
2905
2906/** solving process initialization method of propagator (called when branch and bound process is about to begin) */
2907static
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 */
2938static
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
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 */
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 {
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) );
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
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 */
3051static
3053{ /*lint --e{715}*/
3055
3056 return SCIP_OKAY;
3057}
3058
3059/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3060static
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);
3073
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) */
3123static
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
3136 SCIPpropSetData(prop, NULL);
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
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}
static long bound
SCIP_VAR ** y
SCIP_VAR ** x
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Longint
Definition def.h:171
#define SCIP_REAL_MAX
Definition def.h:187
#define SCIP_INVALID
Definition def.h:206
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define SCIP_REAL_MIN
Definition def.h:188
#define REALABS(x)
Definition def.h:210
#define SCIP_LONGINT_MAX
Definition def.h:172
#define EPSZ(x, eps)
Definition def.h:216
#define SCIP_CALL(x)
Definition def.h:388
int SCIPgetExprNLocksPosNonlinear(SCIP_EXPR *expr)
SCIP_HASHMAP * SCIPgetVarExprHashmapNonlinear(SCIP_CONSHDLR *conshdlr)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
unsigned int SCIPgetExprNSepaUsesActivityNonlinear(SCIP_EXPR *expr)
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)
int SCIPgetExprNLocksNegNonlinear(SCIP_EXPR *expr)
int SCIPgetSubscipDepth(SCIP *scip)
Definition scip_copy.c:2605
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3373
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
SCIP_RETCODE SCIPaddIneqBilinear(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_EXPR *expr, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)
SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition misc.c:11096
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefcutoffbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
SCIP_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_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_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition scip_param.c:269
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition scip_param.c:603
SCIP_RETCODE SCIPincludePropObbt(SCIP *scip)
Definition prop_obbt.c:3146
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition lp.c:17031
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4595
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
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
int SCIPgetNCuts(SCIP *scip)
Definition scip_cut.c:787
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition scip_expr.c:1407
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1421
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition expr.c:3811
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition scip_expr.c:1399
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition scip_lp.c:605
int SCIPgetNLPRows(SCIP *scip)
Definition scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition scip_lp.c:649
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition scip_lp.c:247
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition scip_nlp.c:110
int SCIPgetNNLPVars(SCIP *scip)
Definition scip_nlp.c:201
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition scip_nlp.c:223
SCIP_NLHDLR * SCIPfindNlhdlrNonlinear(SCIP_CONSHDLR *conshdlr, const char *name)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7444
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition scip_prop.c:329
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition prop.c:799
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:151
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition prop.c:789
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:231
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition prop.c:941
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:312
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:167
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:215
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 SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1635
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
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
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition lp.c:17523
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition lp.c:17312
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPchgRelaxfeastol(SCIP *scip, SCIP_Real relaxfeastol)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPdualfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPchgDualfeastol(SCIP *scip, SCIP_Real dualfeastol)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition scip_tree.c:146
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5203
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17611
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17421
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5320
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17432
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18274
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1864
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition scip_var.c:8656
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10041
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIP_Bool lperror
int c
static SCIP_LPSOLSTAT lpsolstat
SCIPendProbing(scip))
SCIP_Bool cutoff
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
int r
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
#define BMSclearMemory(ptr)
Definition memory.h:131
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
bilinear nonlinear handler
generalized variable bounds propagator
#define PROP_DESC
Definition prop_obbt.c:83
static SCIP_Real getFilterCoef(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
Definition prop_obbt.c:476
#define GENVBOUND_PROP_NAME
Definition prop_obbt.c:114
static SCIP_VAR * bilinboundGetY(BILINBOUND *bilinbound)
Definition prop_obbt.c:851
#define DEFAULT_APPLY_FILTERROUNDS
Definition prop_obbt.c:93
#define DEFAULT_BOUNDSTREPS
Definition prop_obbt.c:100
#define DEFAULT_DUALFEASTOL
Definition prop_obbt.c:97
#define PROP_NAME
Definition prop_obbt.c:82
#define DEFAULT_SEPAMINITER
Definition prop_obbt.c:119
static SCIP_RETCODE filterExistingLP(SCIP *scip, SCIP_PROPDATA *propdata, int *nfiltered, BOUND *currbound)
Definition prop_obbt.c:931
#define DEFAULT_FILTERING_MIN
Definition prop_obbt.c:101
#define DEFAULT_MINNONCONVEXITY
Definition prop_obbt.c:127
static unsigned int getScore(SCIP *scip, BOUND *bound, int nlcount, int maxnlcount)
Definition prop_obbt.c:2584
#define DEFAULT_SEPAMAXITER
Definition prop_obbt.c:120
static SCIP_Real bilinboundGetScore(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, BILINBOUND *bilinbound)
Definition prop_obbt.c:885
static SCIP_RETCODE initBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition prop_obbt.c:2702
#define DEFAULT_CONDITIONLIMIT
Definition prop_obbt.c:99
static int nextBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool convexphase)
Definition prop_obbt.c:1614
static SCIP_RETCODE tightenBoundProbing(SCIP *scip, BOUND *bound, SCIP_Real newval, SCIP_Bool *tightened)
Definition prop_obbt.c:1475
static SCIP_Real evalBound(SCIP *scip, BOUND *bound)
Definition prop_obbt.c:1598
#define DEFAULT_TIGHTINTBOUNDSPROBING
Definition prop_obbt.c:107
static SCIP_Bool includeVarGenVBound(SCIP *scip, SCIP_VAR *var)
Definition prop_obbt.c:419
#define DEFAULT_MINITLIMIT
Definition prop_obbt.c:105
#define DEFAULT_ITLIMITFACTOR
Definition prop_obbt.c:103
#define DEFAULT_PROPAGATEFREQ
Definition prop_obbt.c:122
static int bilinboundGetLocksNeg(BILINBOUND *bilinbound)
Definition prop_obbt.c:863
static SCIP_RETCODE filterBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit)
Definition prop_obbt.c:1264
#define DEFAULT_ORDERINGALGO
Definition prop_obbt.c:111
#define DEFAULT_GENVBDSDURINGSEPA
Definition prop_obbt.c:121
static SCIP_RETCODE addObjCutoff(SCIP *scip, SCIP_PROPDATA *propdata)
Definition prop_obbt.c:312
#define DEFAULT_APPLY_TRIVIALFITLERING
Definition prop_obbt.c:95
#define DEFAULT_SEPARATESOL
Definition prop_obbt.c:116
#define OBBT_SCOREBASE
Definition prop_obbt.c:113
#define PROP_DELAY
Definition prop_obbt.c:87
static SCIP_RETCODE solveLP(SCIP *scip, int itlimit, SCIP_Bool *error, SCIP_Bool *optimal)
Definition prop_obbt.c:240
#define DEFAULT_FILTERING_NORM
Definition prop_obbt.c:91
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:797
static int getIterationsLeft(SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)
Definition prop_obbt.c:446
static SCIP_RETCODE filterRound(SCIP *scip, SCIP_PROPDATA *propdata, int itlimit, int *nfiltered, SCIP_Real *objcoefs, int *objcoefsinds, int nobjcoefs)
Definition prop_obbt.c:1104
static SCIP_RETCODE sortBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition prop_obbt.c:1582
#define DEFAULT_CREATE_BILININEQS
Definition prop_obbt.c:124
#define DEFAULT_CREATE_LINCONS
Definition prop_obbt.c:125
#define DEFAULT_TIGHTCONTBOUNDSPROBING
Definition prop_obbt.c:109
#define PROP_TIMING
Definition prop_obbt.c:84
static SCIP_VAR * bilinboundGetX(BILINBOUND *bilinbound)
Definition prop_obbt.c:839
Corner
Definition prop_obbt.c:151
@ LEFTTOP
Definition prop_obbt.c:155
@ RIGHTBOTTOM
Definition prop_obbt.c:153
@ FILTERED
Definition prop_obbt.c:156
@ LEFTBOTTOM
Definition prop_obbt.c:152
@ RIGHTTOP
Definition prop_obbt.c:154
#define DEFAULT_CREATE_GENVBOUNDS
Definition prop_obbt.c:90
enum Corner CORNER
Definition prop_obbt.c:158
static SCIP_RETCODE setObjProbing(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Real coef)
Definition prop_obbt.c:372
#define DEFAULT_ITLIMITFAC_BILININEQS
Definition prop_obbt.c:126
#define DEFAULT_ONLYNONCONVEXVARS
Definition prop_obbt.c:106
#define DEFAULT_RANDSEED
Definition prop_obbt.c:128
static SCIP_RETCODE findNewBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)
Definition prop_obbt.c:1748
static SCIP_Bool varIsFixedLocal(SCIP *scip, SCIP_VAR *var)
Definition prop_obbt.c:362
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:2241
static SCIP_RETCODE applyObbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition prop_obbt.c:1987
static SCIP_RETCODE applyObbtBilinear(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition prop_obbt.c:2389
#define DEFAULT_GENVBDSDURINGFILTER
Definition prop_obbt.c:96
static SCIP_RETCODE createGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Bool *found)
Definition prop_obbt.c:550
static SCIP_RETCODE applyBoundChgs(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
Definition prop_obbt.c:1408
static void getCorner(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *px, SCIP_Real *py)
Definition prop_obbt.c:759
static int bilinboundGetLocksPos(BILINBOUND *bilinbound)
Definition prop_obbt.c:874
static SCIP_RETCODE getNLPVarsNonConvexity(SCIP *scip, unsigned int *nccounts)
Definition prop_obbt.c:2627
static SCIP_RETCODE applySeparation(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *currbound, SCIP_Longint *nleftiterations, SCIP_Bool *success)
Definition prop_obbt.c:1666
#define PROP_FREQ
Definition prop_obbt.c:86
#define PROP_PRIORITY
Definition prop_obbt.c:85
static SCIP_Bool varIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount)
Definition prop_obbt.c:2686
static void exchangeBounds(SCIP_PROPDATA *propdata, int i)
Definition prop_obbt.c:736
optimization-based bound tightening propagator
public methods for managing constraints
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
#define SCIPdebug(x)
Definition pub_message.h:93
#define SCIPdebugMessage
Definition pub_message.h:96
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for NLP management
public methods for propagators
public methods for branch and bound tree
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for propagator plugins
public methods for random numbers
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_Real score
Definition prop_obbt.c:166
unsigned int done
Definition prop_obbt.c:165
SCIP_EXPR * expr
Definition prop_obbt.c:163
unsigned int score
Definition prop_obbt.c:140
unsigned int done
Definition prop_obbt.c:143
unsigned int filtered
Definition prop_obbt.c:141
SCIP_BOUNDTYPE boundtype
Definition prop_obbt.c:139
int index
Definition prop_obbt.c:145
unsigned int found
Definition prop_obbt.c:142
SCIP_Real newval
Definition prop_obbt.c:138
SCIP_VAR * var
Definition prop_obbt.c:137
unsigned int nonconvex
Definition prop_obbt.c:144
#define MAX(x, y)
Definition tclique_def.h:92
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition type_lp.h:51
@ SCIP_BOUNDTYPE_UPPER
Definition type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition type_lp.h:59
@ SCIP_LPSOLSTAT_ERROR
Definition type_lp.h:49
@ SCIP_LPSOLSTAT_NOTSOLVED
Definition type_lp.h:42
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_LPSOLSTAT_TIMELIMIT
Definition type_lp.h:48
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
Definition type_lp.h:45
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition type_lp.h:46
@ SCIP_LPSOLSTAT_ITERLIMIT
Definition type_lp.h:47
@ SCIP_BASESTAT_BASIC
Definition type_lpi.h:92
enum SCIP_BaseStat SCIP_BASESTAT
Definition type_lpi.h:96
#define SCIP_DECL_SORTPTRCOMP(x)
Definition type_misc.h:188
#define SCIP_DECL_PROPCOPY(x)
Definition type_prop.h:61
#define SCIP_DECL_PROPINITSOL(x)
Definition type_prop.h:129
#define SCIP_DECL_PROPFREE(x)
Definition type_prop.h:69
#define SCIP_DECL_PROPEXITSOL(x)
Definition type_prop.h:141
#define SCIP_DECL_PROPRESPROP(x)
Definition type_prop.h:258
struct SCIP_PropData SCIP_PROPDATA
Definition type_prop.h:52
#define SCIP_DECL_PROPEXEC(x)
Definition type_prop.h:217
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_REDUCEDDOM
Definition type_result.h:51
@ SCIP_DIDNOTFIND
Definition type_result.h:44
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51