prop_obbt.c
Go to the documentation of this file.
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 */
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
45 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
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
93 #define DEFAULT_APPLY_FILTERROUNDS FALSE /**< try to filter bounds in so-called filter rounds by solving
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
99 #define DEFAULT_CONDITIONLIMIT -1.0 /**< maximum condition limit used in LP solver (-1.0: no limit) */
103 #define DEFAULT_ITLIMITFACTOR 10.0 /**< multiple of root node LP iterations used as total LP iteration
107 #define DEFAULT_TIGHTINTBOUNDSPROBING TRUE /**< should bounds of integral variables be tightened during
109 #define DEFAULT_TIGHTCONTBOUNDSPROBING FALSE /**< should bounds of continuous variables be tightened during
116 #define DEFAULT_SEPARATESOL FALSE /**< should the obbt LP solution be separated? note that that by
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
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) */
136 {
151 {
157 };
162 {
167 };
183 SCIP_Longint itlimitbilin; /**< total LP iterations limit for solving bilinear inequality LPs */
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 */
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
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? */
219 int ntrivialfiltered; /**< number of filtered bounds because the LP value was equal to the bound */
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 */
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");
340 /* create objective cutoff row; set local flag to FALSE since primal cutoff is globally valid */
342 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, rowname, -SCIPinfinity(scip), SCIPgetCutoffbound(scip), FALSE, FALSE, FALSE) );
417 /** determines whether variable should be included in the right-hand side of the generalized variable bound */
448 SCIP_Longint nolditerations, /**< iterations count at the beginning of the corresponding function */
474 /** returns the objective coefficient for a variable's bound that will be chosen during filtering */
525 * where z is the current cutoff bound. Let (mu, nu, gamma, alpha, beta) >= 0 be the optimal solution of the dual of
546 * that holds for all primal feasible points with objective value at least cutoff_bound. Therefore, the latter
626 /* we need to treat gamma to be exactly 0 if it is below the dual feasibility tolerance, see #2914 */
631 /* we need at least one nonzero coefficient or a nonzero dual multiplier for the objective cutoff */
634 SCIP_Bool addgenvbound; /* if everything is fine with the redcosts and the bounds, add the genvbound */
698 /* check whether the activity of the LVB in the optimal solution of the LP is equal to the LP objective value */
709 SCIP_CALL( SCIPgenVBoundAdd(scip, propdata->genvboundprop, genvboundvars, xi, genvboundcoefs, ncoefs,
732 /** exchange a bound which has been processed and updates the last undone and unfiltered bound index
906 /* penalize small variable domains; TODO tune the factor in the logarithm, maybe add a parameter for it */
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*/
949 SCIPdebugMsg(scip, "can't filter using existing lp solution since it was not solved to optimality\n");
969 /* bound is tight; since this holds for all fixed variables, those are filtered here automatically; if the lp solution
980 SCIPdebugMsg(scip, "trivial filtered var: %s boundval=%e solval=%e\n", SCIPvarGetName(bound->var), boundval, solval);
1242 SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[ objcoefsinds[j] ]->var, objcoefs[j]) );
1301 * 1.) Try first to filter lower bounds of interesting variables, whose bounds are not already filtered
1333 SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1340 while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1343 * 2.) Now try to filter the remaining upper bounds of interesting variables, whose bounds are not already filtered
1388 SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1394 while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1460 SCIPdebug( SCIPdebugMsg(scip, "tightended: %s old: %e new: %e\n" , SCIPvarGetName(bound->var), oldbound,
1551 return bound1->score == bound2->score ? 0 : ( bound1->score > bound2->score ? 1 : -1 ); /*lint !e777*/
1572 diff = (bound1->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0) - (bound2->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0);
1594 }
1610 }
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
1712 SCIPdebug( SCIPdebugMsg(scip, "applySeparation() - optimal=%u error=%u lpiter=%" SCIP_LONGINT_FORMAT "\n", optimal, error, nlpiter); )
1731 SCIP_CALL( tightenBoundProbing(scip, currbound, SCIPvarGetLPSol(currbound->var), &tightened) );
1738 /* leave the separation if we did not tighten the bound and proceed at least propdata->sepaminiter iterations */
1789 while( propdata->lastidx < propdata->nbounds - 1 && !propdata->bounds[propdata->lastidx]->done &&
1859 /* set the objective of currbound to zero to null the whole objective; otherwise the objective is wrong when
1890 SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1897 SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1948 SCIPdebugMsg(scip, "propagation - cutoff %u ndomreds %" SCIP_LONGINT_FORMAT "\n", cutoff, ndomredsfound);
2086 hasconditionlimit = (SCIPgetRealParam(scip, "lp/conditionlimit", &oldconditionlimit) == SCIP_OKAY);
2089 SCIPwarningMessage(scip, "obbt propagator could not set condition limit in LP solver - running without\n");
2091 else if( propdata->conditionlimit > 0.0 && (oldconditionlimit < 0.0 || propdata->conditionlimit < oldconditionlimit) )
2121 /* note that it is not possible to change the objective of non-column variables during probing; we have to take
2145 /* update bound->newval if we have learned additional bound tightenings during SCIPpropagateProbing() */
2146 if( oldlbs != NULL && oldubs != NULL && propdata->npropagatedomreds - lastnpropagatedomreds > 0 )
2153 /* it might be the case that a bound found by the additional propagation is better than the bound found after solving an OBBT
2171 if( bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLbBetter(scip, SCIPvarGetLbLocal(bound->var), oldlb, oldub) )
2173 SCIPdebugMsg(scip, "tighter lower bound due to propagation: %d - %e -> %e\n", i, oldlb, SCIPvarGetLbLocal(bound->var));
2178 if( bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisUbBetter(scip, SCIPvarGetUbLocal(bound->var), oldlb, oldub) )
2180 SCIPdebugMsg(scip, "tighter upper bound due to propagation: %d - %e -> %e\n", i, oldub, SCIPvarGetUbLocal(bound->var));
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
2230 * Let x* be the optimal primal and (mu,theta) be the optimal dual solution of this LP. The KKT conditions imply that
2237 * which is a valid inequality in the (x,y)-space; in order to avoid numerical difficulties when (xs,ys) is too close
2274 SCIPdebugMsg(scip, " solve bilinear LP for (%s,%s) from (%g,%g) to (%g,%g)\n", SCIPvarGetName(x), SCIPvarGetName(y), xs,
2277 /* skip computations if (xs,ys) and (xt,yt) are too close to each other or contain too large values */
2310 SCIPwarningMessage(scip, "Error while solving LP in quadratic constraint handler; LP solve terminated with" \
2318 SCIPdebugMsg(scip, " solved probing LP -> lperror=%u lpstat=%d\n", lperror, SCIPgetLPSolstat(scip));
2337 /* inequality is only useful when both coefficients are different from zero; normalize inequality if possible */
2355 if( SCIPgetLPRows(scip)[r] != row && !SCIPisFeasZero(scip, SCIProwGetDualsol(SCIPgetLPRows(scip)[r])) )
2411 if( propdata->nbilinbounds <= 0 || SCIPgetDepth(scip) != 0 || propdata->lastbilinidx >= propdata->nbilinbounds )
2466 SCIPvarGetName(bilinboundGetX(bilinbound)), SCIPvarGetName(bilinboundGetY(bilinbound)), bilinbound->done,
2523 && SCIPisFeasGT(scip, (xcoef*xt - ycoef*yt - constant) / SQRT(SQR(xcoef) + SQR(ycoef) + SQR(constant)), 1e-2) )
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,
2596 assert(maxnlcount >= nlcount);
2599 score = (unsigned int) ( nlcount > 0 ? (OBBT_SCOREBASE * nlcount * ( OBBT_SCOREBASE - 1 )) / maxnlcount : 0 ); /*lint !e414*/
2676 SCIPdebugMsg(scip, "nccounts[%s] = %u\n", SCIPvarGetName(var), nccounts[SCIPvarGetProbindex(var)]);
2698 }
2710 unsigned int* nccount; /* array that stores in how many nonconvexities each variable appears */
2750 if( varIsInteresting(scip, vars[i], (propdata->onlynonconvexvars ? (int)nccount[i] : nlcount[i])) )
2762 propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2776 propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2831 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata->bilinbounds[propdata->nbilinbounds]) ); /*lint !e866*/
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
2890 * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback. We check
2906 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
2927 propdata->genvboundprop = propdata->creategenvbounds ? SCIPfindProp(scip, GENVBOUND_PROP_NAME) : NULL;
2929 SCIPdebugMsg(scip, "creating genvbounds: %s\n", propdata->genvboundprop != NULL ? "true" : "false");
2950 /* do not run in: presolving, repropagation, probing mode, if no objective propagation is allowed */
2951 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPinRepropagation(scip) || SCIPinProbing(scip) || !SCIPallowWeakDualReds(scip) )
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
3003 if( SCIPgetDepth(scip) > 0 && SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode )
3008 SCIPdebugMsg(scip, "applying obbt for problem <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3010 /* without an optimal LP solution we don't want to run; this may be because propagators with higher priority have
3013 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
3059 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3078 /* note that because we reset filtered flags to false at each call to obbt, the same bound may be filtered multiple
3081 SCIPstatisticMessage("DIVE-LP: %" SCIP_LONGINT_FORMAT " NFILTERED: %d NTRIVIALFILTERED: %d NSOLVED: %d "
3083 propdata->nprobingiterations, propdata->nfiltered, propdata->ntrivialfiltered, propdata->nsolvedbounds,
3084 propdata->nfilterlpiters, propdata->ngenvboundsprobing, propdata->ngenvboundsaggrfil, propdata->ngenvboundstrivfil);
3158 propdata->nprobingiterations = 0;
3171 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
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) );
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) );
3225 "feasibility tolerance for reduced costs used in obbt; this value is used if SCIP's dual feastol is greater",
3257 "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:79
Definition: type_result.h:42
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:491
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5209
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:782
public methods for SCIP parameter handling
static SCIP_RETCODE filterExistingLP(SCIP *scip, SCIP_PROPDATA *propdata, int *nfiltered, BOUND *currbound)
Definition: prop_obbt.c:943
public methods for branch and bound tree
Definition: type_lp.h:48
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:447
static SCIP_RETCODE sortBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:1594
SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1482
Definition: struct_scip.h:68
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1145
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:947
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1695
static SCIP_RETCODE filterRound(SCIP *scip, SCIP_PROPDATA *propdata, int itlimit, int *nfiltered, SCIP_Real *objcoefs, int *objcoefsinds, int nobjcoefs)
Definition: prop_obbt.c:1116
Definition: struct_var.h:207
Definition: prop_obbt.c:164
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:834
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1874
static int nextBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool convexphase)
Definition: prop_obbt.c:1626
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
Definition: type_var.h:62
SCIP_NLHDLR * SCIPfindNlhdlrNonlinear(SCIP_CONSHDLR *conshdlr, const char *name)
Definition: cons_nonlinear.c:13778
Definition: struct_misc.h:268
Definition: prop_obbt.c:173
static SCIP_Real getFilterCoef(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
Definition: prop_obbt.c:488
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:5326
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip_nlp.c:223
static int bilinboundGetLocksPos(BILINBOUND *bilinbound)
Definition: prop_obbt.c:886
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3210
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:447
static void getCorner(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *px, SCIP_Real *py)
Definition: prop_obbt.c:771
Definition: type_lp.h:46
public methods for SCIP variables
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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
Definition: struct_nlhdlr.h:43
SCIP_HASHMAP * SCIPgetVarExprHashmapNonlinear(SCIP_CONSHDLR *conshdlr)
Definition: cons_nonlinear.c:11488
bilinear nonlinear handler
public methods for numerical tolerances
static SCIP_RETCODE tightenBoundProbing(SCIP *scip, BOUND *bound, SCIP_Real newval, SCIP_Bool *tightened)
Definition: prop_obbt.c:1487
public methods for querying solving statistics
static unsigned int getScore(SCIP *scip, BOUND *bound, int nlcount, int maxnlcount)
Definition: prop_obbt.c:2596
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3372
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1130
static SCIP_RETCODE createGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Bool *found)
Definition: prop_obbt.c:562
Definition: struct_misc.h:137
public methods for managing constraints
static SCIP_RETCODE applyBoundChgs(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
Definition: prop_obbt.c:1420
Definition: type_lp.h:49
Definition: type_result.h:44
Definition: prop_obbt.c:147
Definition: struct_cons.h:46
static SCIP_Bool includeVarGenVBound(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:431
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:460
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
Definition: struct_cons.h:126
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
Definition: type_lp.h:56
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:2143
Definition: prop_obbt.c:168
Definition: type_var.h:51
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
SCIP_RETCODE SCIPchgDualfeastol(SCIP *scip, SCIP_Real dualfeastol)
Definition: scip_numerics.c:296
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
Definition: type_retcode.h:42
static SCIP_Bool varIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount)
Definition: prop_obbt.c:2698
public methods for problem copies
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
Definition: scip_probing.c:388
static SCIP_Real bilinboundGetScore(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, BILINBOUND *bilinbound)
Definition: prop_obbt.c:897
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:821
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:819
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:808
Definition: type_result.h:51
static int getIterationsLeft(SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)
Definition: prop_obbt.c:458
Definition: type_lp.h:43
Definition: struct_prop.h:46
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:56
Definition: struct_expr.h:104
static SCIP_RETCODE solveBilinearLP(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real xs, SCIP_Real ys, SCIP_Real xt, SCIP_Real yt, SCIP_Real *xcoef, SCIP_Real *ycoef, SCIP_Real *constant, SCIP_Longint iterlim, int *nnonzduals)
Definition: prop_obbt.c:2253
int SCIPgetExprNLocksNegNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12776
public data structures and miscellaneous methods
Definition: type_var.h:64
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1416
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: type_var.h:63
optimization-based bound tightening propagator
Definition: struct_lp.h:201
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
public methods for LP management
public methods for cuts and aggregation rows
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
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:1678
static SCIP_RETCODE setObjProbing(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Real coef)
Definition: prop_obbt.c:384
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:231
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10034
public methods for the LP relaxation, rows and columns
SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1527
public methods for nonlinear relaxation
Definition: type_lp.h:45
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:1559
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:17851
static SCIP_RETCODE solveLP(SCIP *scip, int itlimit, SCIP_Bool *error, SCIP_Bool *optimal)
Definition: prop_obbt.c:252
int SCIPgetExprNLocksPosNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12765
general public methods
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:486
public methods for random numbers
Definition: type_lp.h:57
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
Definition: scip_probing.c:907
public methods for message output
static SCIP_RETCODE findNewBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)
Definition: prop_obbt.c:1760
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:215
int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1543
public methods for message handling
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
static int bilinboundGetLocksNeg(BILINBOUND *bilinbound)
Definition: prop_obbt.c:875
static SCIP_RETCODE filterBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit)
Definition: prop_obbt.c:1276
public methods for propagator plugins
SCIP_Real SCIPchgRelaxfeastol(SCIP *scip, SCIP_Real relaxfeastol)
Definition: scip_numerics.c:354
static SCIP_RETCODE addObjCutoff(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:324
static SCIP_Bool varIsFixedLocal(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:374
Definition: type_set.h:53
static SCIP_RETCODE getNLPVarsNonConvexity(SCIP *scip, unsigned int *nccounts)
Definition: prop_obbt.c:2639
Definition: type_lp.h:44
Definition: type_lp.h:42
Definition: type_lp.h:47
unsigned int SCIPgetExprNSepaUsesActivityNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12895
Definition: type_lpi.h:92
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12790
static SCIP_RETCODE initBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:2714
Definition: objbenders.h:43
Definition: prop_obbt.c:165
Definition: prop_obbt.c:167
public methods for global and local (sub)problems
static SCIP_RETCODE applyObbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:1999
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
Definition: prop_obbt.c:166
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
static SCIP_RETCODE applyObbtBilinear(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:2401
Definition: type_result.h:48
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
static void getCorners(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real *xt, SCIP_Real *yt)
Definition: prop_obbt.c:809
public methods for propagators
generalized variable bounds propagator
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:114
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:474
Definition: type_var.h:67