prop_obbt.c
Go to the documentation of this file.
23 /**@todo if bound tightenings of other propagators are the reason for lpsolstat != SCIP_LPSOLSTAT_OPTIMAL, resolve LP */
24 /**@todo only run more than once in root node if primal bound improved or many cuts were added to the LP */
25 /**@todo filter bounds of a variable already if SCIPisLbBetter()/SCIPisUbBetter() would return FALSE */
31 /**@todo implement conflict resolving callback by calling public method of genvbounds propagator, since the reason are
32 * exactly the variable bounds with nonnegative reduced costs stored in the right-hand side of the generated
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
81 #define DEFAULT_CREATE_GENVBOUNDS TRUE /**< should obbt try to provide genvbounds if possible? */
82 #define DEFAULT_FILTERING_NORM TRUE /**< should coefficients in filtering be normalized w.r.t. the
84 #define DEFAULT_APPLY_FILTERROUNDS FALSE /**< try to filter bounds in so-called filter rounds by solving
86 #define DEFAULT_APPLY_TRIVIALFITLERING TRUE /**< should obbt try to use the LP solution to filter some bounds? */
87 #define DEFAULT_GENVBDSDURINGFILTER TRUE /**< try to genrate genvbounds during trivial and aggressive filtering? */
88 #define DEFAULT_DUALFEASTOL 1e-9 /**< feasibility tolerance for reduced costs used in obbt; this value
90 #define DEFAULT_CONDITIONLIMIT -1.0 /**< maximum condition limit used in LP solver (-1.0: no limit) */
94 #define DEFAULT_ITLIMITFACTOR 10.0 /**< multiple of root node LP iterations used as total LP iteration
98 #define DEFAULT_TIGHTINTBOUNDSPROBING TRUE /**< should bounds of integral variables be tightened during
100 #define DEFAULT_TIGHTCONTBOUNDSPROBING FALSE /**< should bounds of continuous variables be tightened during
107 #define DEFAULT_SEPARATESOL FALSE /**< should the obbt LP solution be separated? note that that by
110 #define DEFAULT_SEPAMINITER 0 /**< minimum number of iteration spend to separate an obbt LP solution */
111 #define DEFAULT_SEPAMAXITER 10 /**< maximum number of iteration spend to separate an obbt LP solution */
112 #define DEFAULT_GENVBDSDURINGSEPA TRUE /**< try to create genvbounds during separation process? */
113 #define DEFAULT_PROPAGATEFREQ 0 /**< trigger a propagation round after that many bound tightenings
115 #define DEFAULT_CREATE_BILININEQS TRUE /**< solve auxiliary LPs in order to find valid inequalities for bilinear terms? */
116 #define DEFAULT_CREATE_LINCONS FALSE /**< create linear constraints from inequalities for bilinear terms? */
117 #define DEFAULT_ITLIMITFAC_BILININEQS 3.0 /**< multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit) */
127 {
142 {
148 };
153 {
158 };
174 SCIP_Longint itlimitbilin; /**< total LP iterations limit for solving bilinear inequality LPs */
182 SCIP_Real itlimitfactorbilin; /**< multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit) */
183 SCIP_Real minnonconvexity; /**< lower bound on minimum absolute value of nonconvex eigenvalues for a bilinear term */
185 SCIP_Bool applytrivialfilter; /**< should obbt try to use the LP solution to filter some bounds? */
186 SCIP_Bool genvbdsduringfilter;/**< should we try to generate genvbounds during trivial and aggressive
200 SCIP_Bool createbilinineqs; /**< solve auxiliary LPs in order to find valid inequalities for bilinear terms? */
201 SCIP_Bool createlincons; /**< create linear constraints from inequalities for bilinear terms? */
210 int ntrivialfiltered; /**< number of filtered bounds because the LP value was equal to the bound */
212 int ngenvboundsprobing; /**< number of non-trivial genvbounds generated and added during obbt */
213 int ngenvboundsaggrfil; /**< number of non-trivial genvbounds found during aggressive filtering */
256 SCIPwarningMessage(scip, " error while solving LP in obbt propagator; LP solve terminated with code <%d>\n", retcode);
257 SCIPwarningMessage(scip, " this does not affect the remaining solution procedure --> continue\n");
331 /* create objective cutoff row; set local flag to FALSE since primal cutoff is globally valid */
333 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, rowname, -SCIPinfinity(scip), SCIPgetCutoffbound(scip), FALSE, FALSE, FALSE) );
408 /** determines whether variable should be included in the right-hand side of the generalized variable bound */
439 SCIP_Longint nolditerations, /**< iterations count at the beginning of the corresponding function */
465 /** returns the objective coefficient for a variable's bound that will be chosen during filtering */
516 * where z is the current cutoff bound. Let (mu, nu, gamma, alpha, beta) >= 0 be the optimal solution of the dual of
537 * that holds for all primal feasible points with objective value at least cutoff_bound. Therefore, the latter
617 /* we need to treat gamma to be exactly 0 if it is below the dual feasibility tolerance, see #2914 */
622 /* we need at least one nonzero coefficient or a nonzero dual multiplier for the objective cutoff */
625 SCIP_Bool addgenvbound; /* if everything is fine with the redcosts and the bounds, add the genvbound */
689 /* check whether the activity of the LVB in the optimal solution of the LP is equal to the LP objective value */
700 SCIP_CALL( SCIPgenVBoundAdd(scip, propdata->genvboundprop, genvboundvars, xi, genvboundcoefs, ncoefs,
723 /** exchange a bound which has been processed and updates the last undone and unfiltered bound index
897 /* penalize small variable domains; TODO tune the factor in the logarithm, maybe add a parameter for it */
908 SCIP_Real interiorityx = MIN(solx-lbx, ubx-solx) / MAX(ubx-lbx, SCIPepsilon(scip)); /*lint !e666*/
909 SCIP_Real interiorityy = MIN(soly-lby, uby-soly) / MAX(uby-lby, SCIPepsilon(scip)); /*lint !e666*/
940 SCIPdebugMsg(scip, "can't filter using existing lp solution since it was not solved to optimality\n");
960 /* bound is tight; since this holds for all fixed variables, those are filtered here automatically; if the lp solution
971 SCIPdebugMsg(scip, "trivial filtered var: %s boundval=%e solval=%e\n", SCIPvarGetName(bound->var), boundval, solval);
1233 SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[ objcoefsinds[j] ]->var, objcoefs[j]) );
1292 * 1.) Try first to filter lower bounds of interesting variables, whose bounds are not already filtered
1324 SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1331 while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1334 * 2.) Now try to filter the remaining upper bounds of interesting variables, whose bounds are not already filtered
1379 SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1385 while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1451 SCIPdebug( SCIPdebugMsg(scip, "tightended: %s old: %e new: %e\n" , SCIPvarGetName(bound->var), oldbound,
1542 return bound1->score == bound2->score ? 0 : ( bound1->score > bound2->score ? 1 : -1 ); /*lint !e777*/
1563 diff = (bound1->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0) - (bound2->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0);
1585 }
1601 }
1652 /** try to separate the solution of the last OBBT LP in order to learn better variable bounds; we apply additional
1653 * separation rounds as long as the routine finds better bounds; because of dual degeneracy we apply a minimum number of
1703 SCIPdebug( SCIPdebugMsg(scip, "applySeparation() - optimal=%u error=%u lpiter=%" SCIP_LONGINT_FORMAT "\n", optimal, error, nlpiter); )
1722 SCIP_CALL( tightenBoundProbing(scip, currbound, SCIPvarGetLPSol(currbound->var), &tightened) );
1729 /* leave the separation if we did not tighten the bound and proceed at least propdata->sepaminiter iterations */
1780 while( propdata->lastidx < propdata->nbounds - 1 && !propdata->bounds[propdata->lastidx]->done &&
1850 /* set the objective of currbound to zero to null the whole objective; otherwise the objective is wrong when
1881 SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1888 SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1939 SCIPdebugMsg(scip, "propagation - cutoff %u ndomreds %" SCIP_LONGINT_FORMAT "\n", cutoff, ndomredsfound);
2077 hasconditionlimit = (SCIPgetRealParam(scip, "lp/conditionlimit", &oldconditionlimit) == SCIP_OKAY);
2080 SCIPwarningMessage(scip, "obbt propagator could not set condition limit in LP solver - running without\n");
2082 else if( propdata->conditionlimit > 0.0 && (oldconditionlimit < 0.0 || propdata->conditionlimit < oldconditionlimit) )
2112 /* note that it is not possible to change the objective of non-column variables during probing; we have to take
2136 /* update bound->newval if we have learned additional bound tightenings during SCIPpropagateProbing() */
2137 if( oldlbs != NULL && oldubs != NULL && propdata->npropagatedomreds - lastnpropagatedomreds > 0 )
2144 /* it might be the case that a bound found by the additional propagation is better than the bound found after solving an OBBT
2162 if( bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLbBetter(scip, SCIPvarGetLbLocal(bound->var), oldlb, oldub) )
2164 SCIPdebugMsg(scip, "tighter lower bound due to propagation: %d - %e -> %e\n", i, oldlb, SCIPvarGetLbLocal(bound->var));
2169 if( bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisUbBetter(scip, SCIPvarGetUbLocal(bound->var), oldlb, oldub) )
2171 SCIPdebugMsg(scip, "tighter upper bound due to propagation: %d - %e -> %e\n", i, oldub, SCIPvarGetUbLocal(bound->var));
2206 /** computes a valid inequality from the current LP relaxation for a bilinear term xy only involving x and y; the
2207 * inequality is found by optimizing along the line connecting the points (xs,ys) and (xt,yt) over the currently given
2221 * Let x* be the optimal primal and (mu,theta) be the optimal dual solution of this LP. The KKT conditions imply that
2228 * which is a valid inequality in the (x,y)-space; in order to avoid numerical difficulties when (xs,ys) is too close
2265 SCIPdebugMsg(scip, " solve bilinear LP for (%s,%s) from (%g,%g) to (%g,%g)\n", SCIPvarGetName(x), SCIPvarGetName(y), xs,
2268 /* skip computations if (xs,ys) and (xt,yt) are too close to each other or contain too large values */
2301 SCIPwarningMessage(scip, "Error while solving LP in quadratic constraint handler; LP solve terminated with" \
2309 SCIPdebugMsg(scip, " solved probing LP -> lperror=%u lpstat=%d\n", lperror, SCIPgetLPSolstat(scip));
2328 /* inequality is only useful when both coefficients are different from zero; normalize inequality if possible */
2346 if( SCIPgetLPRows(scip)[r] != row && !SCIPisFeasZero(scip, SCIProwGetDualsol(SCIPgetLPRows(scip)[r])) )
2402 if( propdata->nbilinbounds <= 0 || SCIPgetDepth(scip) != 0 || propdata->lastbilinidx >= propdata->nbilinbounds )
2457 SCIPvarGetName(bilinboundGetX(bilinbound)), SCIPvarGetName(bilinboundGetY(bilinbound)), bilinbound->done,
2514 && SCIPisFeasGT(scip, (xcoef*xt - ycoef*yt - constant) / SQRT(SQR(xcoef) + SQR(ycoef) + SQR(constant)), 1e-2) )
2538 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "bilincons_%s_%s", SCIPvarGetName(x), SCIPvarGetName(y));
2539 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 2, linvars, linvals, -SCIPinfinity(scip), rhs,
2587 assert(maxnlcount >= nlcount);
2590 score = (unsigned int) ( nlcount > 0 ? (OBBT_SCOREBASE * nlcount * ( OBBT_SCOREBASE - 1 )) / maxnlcount : 0 ); /*lint !e414*/
2667 SCIPdebugMsg(scip, "nccounts[%s] = %u\n", SCIPvarGetName(var), nccounts[SCIPvarGetProbindex(var)]);
2689 }
2701 unsigned int* nccount; /* array that stores in how many nonconvexities each variable appears */
2741 if( varIsInteresting(scip, vars[i], (propdata->onlynonconvexvars ? (int)nccount[i] : nlcount[i])) )
2753 propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2767 propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2822 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata->bilinbounds[propdata->nbilinbounds]) ); /*lint !e866*/
2865 /* sort bounds according to decreasing score; although this initial order will be overruled by the distance
2866 * criterion later, gives a more well-defined starting situation for OBBT and might help to reduce solver
2881 * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback. We check
2897 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
2918 propdata->genvboundprop = propdata->creategenvbounds ? SCIPfindProp(scip, GENVBOUND_PROP_NAME) : NULL;
2920 SCIPdebugMsg(scip, "creating genvbounds: %s\n", propdata->genvboundprop != NULL ? "true" : "false");
2941 /* do not run in: presolving, repropagation, probing mode, if no objective propagation is allowed */
2942 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPinRepropagation(scip) || SCIPinProbing(scip) || !SCIPallowWeakDualReds(scip) )
2956 /* only run if LP all columns are in the LP, i.e., the LP is a relaxation; e.g., do not run if pricers are active
2994 if( SCIPgetDepth(scip) > 0 && SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode )
2999 SCIPdebugMsg(scip, "applying obbt for problem <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3001 /* without an optimal LP solution we don't want to run; this may be because propagators with higher priority have
3004 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
3050 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3069 /* note that because we reset filtered flags to false at each call to obbt, the same bound may be filtered multiple
3072 SCIPstatisticMessage("DIVE-LP: %" SCIP_LONGINT_FORMAT " NFILTERED: %d NTRIVIALFILTERED: %d NSOLVED: %d "
3074 propdata->nprobingiterations, propdata->nfiltered, propdata->ntrivialfiltered, propdata->nsolvedbounds,
3075 propdata->nfilterlpiters, propdata->ngenvboundsprobing, propdata->ngenvboundsaggrfil, propdata->ngenvboundstrivfil);
3149 propdata->nprobingiterations = 0;
3162 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
3200 "multiple of root node LP iterations used as total LP iteration limit for obbt (<= 0: no limit )",
3201 &propdata->itlimitfactor, FALSE, DEFAULT_ITLIMITFACTOR, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3204 "multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit)",
3205 &propdata->itlimitfactorbilin, FALSE, DEFAULT_ITLIMITFAC_BILININEQS, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3216 "feasibility tolerance for reduced costs used in obbt; this value is used if SCIP's dual feastol is greater",
3248 "select the type of ordering algorithm which should be used (0: no special ordering, 1: greedy, 2: greedy reverse)",
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
Definition: type_result.h:33
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:482
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
public methods for SCIP parameter handling
static SCIP_RETCODE filterExistingLP(SCIP *scip, SCIP_PROPDATA *propdata, int *nfiltered, BOUND *currbound)
Definition: prop_obbt.c:934
public methods for branch and bound tree
Definition: type_lp.h:39
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:438
static SCIP_RETCODE sortBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:1585
SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1473
Definition: struct_scip.h:59
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1136
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:938
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
static SCIP_RETCODE filterRound(SCIP *scip, SCIP_PROPDATA *propdata, int itlimit, int *nfiltered, SCIP_Real *objcoefs, int *objcoefsinds, int nobjcoefs)
Definition: prop_obbt.c:1107
Definition: struct_var.h:198
Definition: prop_obbt.c:155
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
static int nextBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool convexphase)
Definition: prop_obbt.c:1617
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
Definition: type_var.h:53
SCIP_NLHDLR * SCIPfindNlhdlrNonlinear(SCIP_CONSHDLR *conshdlr, const char *name)
Definition: cons_nonlinear.c:13765
Definition: struct_misc.h:259
Definition: prop_obbt.c:164
static SCIP_Real getFilterCoef(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
Definition: prop_obbt.c:479
public methods for problem variables
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip_nlp.c:214
static int bilinboundGetLocksPos(BILINBOUND *bilinbound)
Definition: prop_obbt.c:877
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
static void getCorner(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *px, SCIP_Real *py)
Definition: prop_obbt.c:762
Definition: type_lp.h:37
public methods for SCIP variables
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.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:74
Definition: struct_nlhdlr.h:34
SCIP_HASHMAP * SCIPgetVarExprHashmapNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:11475
bilinear nonlinear handler
public methods for numerical tolerances
static SCIP_RETCODE tightenBoundProbing(SCIP *scip, BOUND *bound, SCIP_Real newval, SCIP_Bool *tightened)
Definition: prop_obbt.c:1478
public methods for querying solving statistics
static unsigned int getScore(SCIP *scip, BOUND *bound, int nlcount, int maxnlcount)
Definition: prop_obbt.c:2587
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1121
static SCIP_RETCODE createGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Bool *found)
Definition: prop_obbt.c:553
Definition: struct_misc.h:128
public methods for managing constraints
static SCIP_RETCODE applyBoundChgs(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
Definition: prop_obbt.c:1411
Definition: type_lp.h:40
Definition: type_result.h:35
Definition: prop_obbt.c:138
Definition: struct_cons.h:37
static SCIP_Bool includeVarGenVBound(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:422
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
Definition: struct_cons.h:117
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
Definition: type_lp.h:47
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefcutoffbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
Definition: prop_genvbounds.c:2134
Definition: prop_obbt.c:159
Definition: type_var.h:42
SCIP_RETCODE SCIPseparateSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool pretendroot, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition: scip_cut.c:726
SCIP_RETCODE SCIPchgDualfeastol(SCIP *scip, SCIP_Real dualfeastol)
Definition: scip_numerics.c:287
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
Definition: type_retcode.h:33
static SCIP_Bool varIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount)
Definition: prop_obbt.c:2689
public methods for problem copies
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
Definition: scip_probing.c:379
static SCIP_Real bilinboundGetScore(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, BILINBOUND *bilinbound)
Definition: prop_obbt.c:888
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
Definition: type_result.h:42
static int getIterationsLeft(SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)
Definition: prop_obbt.c:449
Definition: type_lp.h:34
Definition: struct_prop.h:37
public methods for constraint handler plugins and constraints
public methods for NLP management
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
Definition: struct_expr.h:95
static SCIP_RETCODE solveBilinearLP(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real xs, SCIP_Real ys, SCIP_Real xt, SCIP_Real yt, SCIP_Real *xcoef, SCIP_Real *ycoef, SCIP_Real *constant, SCIP_Longint iterlim, int *nnonzduals)
Definition: prop_obbt.c:2244
int SCIPgetExprNLocksNegNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12763
public data structures and miscellaneous methods
Definition: type_var.h:55
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: type_var.h:54
optimization-based bound tightening propagator
Definition: struct_lp.h:192
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
public methods for LP management
public methods for cuts and aggregation rows
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE applySeparation(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *currbound, SCIP_Longint *nleftiterations, SCIP_Bool *success)
Definition: prop_obbt.c:1669
static SCIP_RETCODE setObjProbing(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Real coef)
Definition: prop_obbt.c:375
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
public methods for the LP relaxation, rows and columns
SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1518
public methods for nonlinear relaxation
Definition: type_lp.h:36
methods for sorting joint arrays of various types
SCIP_RETCODE SCIPaddIneqBilinear(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_EXPR *expr, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)
Definition: nlhdlr_bilinear.c:1550
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)
Definition: cons_linear.c:17821
static SCIP_RETCODE solveLP(SCIP *scip, int itlimit, SCIP_Bool *error, SCIP_Bool *optimal)
Definition: prop_obbt.c:243
int SCIPgetExprNLocksPosNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12752
general public methods
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
public methods for random numbers
Definition: type_lp.h:48
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
Definition: scip_probing.c:898
public methods for message output
static SCIP_RETCODE findNewBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)
Definition: prop_obbt.c:1751
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1534
public methods for message handling
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
static int bilinboundGetLocksNeg(BILINBOUND *bilinbound)
Definition: prop_obbt.c:866
static SCIP_RETCODE filterBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit)
Definition: prop_obbt.c:1267
public methods for propagator plugins
SCIP_Real SCIPchgRelaxfeastol(SCIP *scip, SCIP_Real relaxfeastol)
Definition: scip_numerics.c:345
static SCIP_RETCODE addObjCutoff(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:315
static SCIP_Bool varIsFixedLocal(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:365
Definition: type_set.h:44
static SCIP_RETCODE getNLPVarsNonConvexity(SCIP *scip, unsigned int *nccounts)
Definition: prop_obbt.c:2630
Definition: type_lp.h:35
Definition: type_lp.h:33
Definition: type_lp.h:38
unsigned int SCIPgetExprNSepaUsesActivityNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12882
Definition: type_lpi.h:83
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12777
SCIPallocBlockMemory(scip, subsol))
static SCIP_RETCODE initBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:2705
Definition: objbenders.h:33
Definition: prop_obbt.c:156
Definition: prop_obbt.c:158
public methods for global and local (sub)problems
static SCIP_RETCODE applyObbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:1990
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
Definition: prop_obbt.c:157
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
static SCIP_RETCODE applyObbtBilinear(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:2392
Definition: type_result.h:39
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
static void getCorners(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real *xt, SCIP_Real *yt)
Definition: prop_obbt.c:800
public methods for propagators
generalized variable bounds propagator
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:465
Definition: type_var.h:58