83#define PROP_NAME "obbt"
84#define PROP_DESC "optimization-based bound tightening propagator"
85#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
86#define PROP_PRIORITY -1000000
88#define PROP_DELAY TRUE
91#define DEFAULT_CREATE_GENVBOUNDS TRUE
92#define DEFAULT_FILTERING_NORM TRUE
94#define DEFAULT_APPLY_FILTERROUNDS FALSE
96#define DEFAULT_APPLY_TRIVIALFITLERING TRUE
97#define DEFAULT_GENVBDSDURINGFILTER TRUE
98#define DEFAULT_DUALFEASTOL 1e-9
100#define DEFAULT_CONDITIONLIMIT -1.0
101#define DEFAULT_BOUNDSTREPS 0.001
102#define DEFAULT_FILTERING_MIN 2
104#define DEFAULT_ITLIMITFACTOR 10.0
106#define DEFAULT_MINITLIMIT 5000L
107#define DEFAULT_ONLYNONCONVEXVARS TRUE
108#define DEFAULT_INDICATORS FALSE
109#define DEFAULT_INDICATORTHRESHOLD 1e6
111#define DEFAULT_TIGHTINTBOUNDSPROBING TRUE
113#define DEFAULT_TIGHTCONTBOUNDSPROBING FALSE
115#define DEFAULT_ORDERINGALGO 1
117#define OBBT_SCOREBASE 5
118#define GENVBOUND_PROP_NAME "genvbounds"
120#define DEFAULT_SEPARATESOL FALSE
123#define DEFAULT_SEPAMINITER 0
124#define DEFAULT_SEPAMAXITER 10
125#define DEFAULT_GENVBDSDURINGSEPA TRUE
126#define DEFAULT_PROPAGATEFREQ 0
128#define DEFAULT_CREATE_BILININEQS TRUE
129#define DEFAULT_CREATE_LINCONS FALSE
130#define DEFAULT_ITLIMITFAC_BILININEQS 3.0
131#define DEFAULT_MINNONCONVEXITY 1e-1
132#define DEFAULT_RANDSEED 149
226 int ntrivialfiltered;
228 int ngenvboundsprobing;
229 int ngenvboundsaggrfil;
230 int ngenvboundstrivfil;
237 int propagatecounter;
258 assert(itlimit == -1 || itlimit >= 0);
272 SCIPwarningMessage(
scip,
" error while solving LP in obbt propagator; LP solve terminated with code <%d>\n", retcode);
361 propdata->cutoffrow = row;
418 assert((counter == 0 && coef == 0.0) || (counter == 1 && coef != 0.0));
462 assert(nolditerations >= 0);
463 assert(itlimit == -1 || itlimit >= 0);
473 itsleft =
MAX(itsleft, 0);
474 itsleft =
MIN(itsleft, INT_MAX);
477 return (
int) itsleft;
509 if( propdata->normalize )
609 for( k = 0; k <
nvars; k++ )
619 if( propdata->cutoffrow ==
NULL )
639 if( ncoefs > 0 || gamma_dual != 0.0 )
663 for( k = 0; k <
nvars; k++ )
682 addgenvbound =
FALSE;
688 genvboundvars[idx] = xk;
689 genvboundcoefs[idx] = redcost;
699 assert(!addgenvbound || idx == ncoefs);
708 for( k = 0; k < ncoefs; ++k )
749 assert(propdata->lastidx >= 0 && propdata->lastidx < propdata->nbounds);
752 if( propdata->lastidx !=
i )
756 tmp = propdata->bounds[
i];
757 propdata->bounds[
i] = propdata->bounds[propdata->lastidx];
758 propdata->bounds[propdata->lastidx] = tmp;
761 propdata->lastidx -= 1;
914 if( ubx - lbx < 0.5 )
916 if( uby - lby < 0.5 )
927 score += interiorityx + interiorityy;
953 if( nlcount == 0 && nindcount > 0 )
982 SCIPdebugMsg(
scip,
"can't filter using existing lp solution since it was not solved to optimality\n");
987 for(
i = propdata->nbounds - 1;
i >= 0; --
i )
994 bound = propdata->bounds[
i];
1046 assert(propdata->nprobingiterations >= 0);
1049 if( optimal && propdata->genvboundprop !=
NULL
1059 propdata->ngenvboundstrivfil += 1;
1070 if( propdata->lastidx >= 0 )
1082 BILINBOUND* bilinbound = propdata->bilinbounds[
i];
1108 for( j = 0; j < 4; ++j )
1121 if( oldfiltered != bilinbound->
filtered )
1125 SCIPdebugMessage(
"filtered corners %d for (%s,%s) = (%g,%g) in [%g,%g]x[%g,%g]\n",
1158 assert(itlimit == -1 || itlimit >= 0);
1173 assert(propdata->nfilterlpiters >= 0);
1177 SCIPdebugMsg(
scip,
"skipping filter round since the LP was not solved to optimality\n");
1184 for(
i = 0;
i < propdata->nbounds;
i++ )
1191 bound = propdata->bounds[
i];
1194 if(
bound->filtered )
1223 for( j = 0; j < nobjcoefs; ++j )
1227 filterbound = propdata->bounds[ objcoefsinds[j] ];
1234 for( j = 0; j <
nvars; ++j )
1245 assert(propdata->nfilterlpiters >= 0);
1248 if( optimal && propdata->genvboundprop !=
NULL
1258 propdata->ngenvboundsaggrfil += 1;
1264 for( j = 0; j < nobjcoefs; ++j )
1268 filterbound = propdata->bounds[ objcoefsinds[j] ];
1309 int nleftiterations;
1318 assert(itlimit == -1 || itlimit >= 0);
1336 for(
i = 0;
i < propdata->nbounds;
i++ )
1338 if( !propdata->bounds[
i]->filtered && !propdata->bounds[
i]->done && propdata->bounds[
i]->indicator && !propdata->bounds[
i]->nonconvex )
1343 propdata->bounds[
i]->filtered =
TRUE;
1360 for(
i = 0;
i < propdata->nbounds;
i++ )
1363 && !propdata->bounds[
i]->done )
1374 objcoefs[nobjcoefs] = objcoef;
1375 objcoefsinds[nobjcoefs] =
i;
1385 ntotalfiltered += nfiltered;
1386 SCIPdebugMsg(
scip,
"filtered %d more bounds in lower bounds round\n", nfiltered);
1391 while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1398 for(
i = 0;
i < nobjcoefs;
i++ )
1402 assert(objcoefsinds[
i] >= 0 && objcoefsinds[
i] < propdata->nbounds);
1403 bound = propdata->bounds[ objcoefsinds[
i] ];
1416 for(
i = 0;
i < propdata->nbounds;
i++ )
1429 objcoefs[nobjcoefs] = objcoef;
1430 objcoefsinds[nobjcoefs] =
i;
1440 SCIPdebugMsg(
scip,
"filtered %d more bounds in upper bounds round\n", nfiltered);
1441 ntotalfiltered += nfiltered;
1445 while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1448 propdata->nfiltered += ntotalfiltered;
1478 for(
i = 0;
i < propdata->nbounds;
i++ )
1484 bound = propdata->bounds[
i];
1622 diff = (!bound1->
done ? 1 : 0) - (!bound2->
done ? 1 : 0);
1650 SCIPsortDownPtr((
void**) propdata->bounds, compBoundsBoundtype, propdata->nbounds);
1689 for( k = 0; k <= propdata->lastidx; ++k )
1692 tmpbound = propdata->bounds[k];
1702 if( propdata->orderingalgo == 0 )
1708 boundval = (propdata->orderingalgo == 2) ? -1.0 * boundval : boundval;
1710 if( bestidx == -1 || boundval < bestval )
1746 for(
i = 0;
i <= propdata->sepamaxiter; ++
i )
1776 if( error || !optimal )
1780 if( inroot && propdata->genvboundprop !=
NULL && propdata->genvbdsduringsepa )
1784 propdata->ngenvboundsprobing += found ? 1 : 0;
1792 SCIPdebugMsg(
scip,
"apply separation - tightened=%u oldval=%e newval=%e\n", tightened, oldval,
1795 *success |= tightened;
1799 if( !tightened &&
i >= propdata->sepaminiter )
1827 itlimit = *nleftiterations;
1829 iterationsleft = (*nleftiterations == -1) || (*nleftiterations > 0);
1841 if( propdata->bounds[0]->done || propdata->bounds[0]->filtered )
1848 propdata->lastidx = 0;
1849 while( propdata->lastidx < propdata->nbounds - 1 && !propdata->bounds[propdata->lastidx]->done &&
1850 !propdata->bounds[propdata->lastidx]->filtered )
1851 ++propdata->lastidx;
1860 if( nextboundidx == -1 )
1866 currbound = propdata->bounds[nextboundidx];
1901 propdata->nsolvedbounds++;
1913 iterationsleft = (*nleftiterations == -1) || (*nleftiterations > 0);
1936 && propdata->genvboundprop !=
NULL )
1943 propdata->ngenvboundsprobing += 1;
1953 SCIPdebugMsg(
scip,
"tightening bound %s\n", success ?
"successful" :
"not successful");
1960 SCIPdebugMsg(
scip,
"tightening bound %s\n", success ?
"successful" :
"not successful");
1964 if( iterationsleft && propdata->separatesol )
1992 if( propdata->applytrivialfilter )
1995 SCIPdebugMsg(
scip,
"filtered %d bounds via inspecting present LP solution\n", nfiltered);
1996 propdata->ntrivialfiltered += nfiltered;
1999 propdata->propagatecounter += success ? 1 : 0;
2002 if( propdata->propagatefreq != 0 && propdata->propagatecounter >= propdata->propagatefreq )
2010 propdata->npropagatedomreds += ndomredsfound;
2011 propdata->propagatecounter = 0;
2022 if( nextboundidx == -1 )
2028 currbound = propdata->bounds[nextboundidx];
2032 if( iterationsleft )
2072 assert(itlimit == -1 || itlimit >= 0);
2078 lastnpropagatedomreds = propdata->npropagatedomreds;
2079 nleftiterations = itlimit;
2081 propdata->lastidx = -1;
2086 if( propdata->propagatefreq > 0 )
2093 for(
i = 0;
i < propdata->nbounds;
i++ )
2099 if( oldlbs !=
NULL && oldubs !=
NULL )
2125 if( propdata->applytrivialfilter && !continuenode )
2128 SCIPdebugMsg(
scip,
"filtered %d bounds via inspecting present LP solution\n", nfiltered);
2129 propdata->ntrivialfiltered += nfiltered;
2140 if( propdata->dualfeastol < olddualfeastol )
2147 if( !hasconditionlimit )
2149 SCIPwarningMessage(
scip,
"obbt propagator could not set condition limit in LP solver - running without\n");
2151 else if( propdata->conditionlimit > 0.0 && (oldconditionlimit < 0.0 || propdata->conditionlimit < oldconditionlimit) )
2158 if( !
SCIPisEQ(
scip, oldboundstreps, propdata->boundstreps) )
2171 if( propdata->applyfilterrounds )
2193 if( nleftiterations > 0 || itlimit < 0 )
2200 if( hasconditionlimit )
2206 if( oldlbs !=
NULL && oldubs !=
NULL && propdata->npropagatedomreds - lastnpropagatedomreds > 0 )
2208 assert(propdata->propagatefreq > 0);
2209 for(
i = 0;
i < propdata->nbounds; ++
i )
2228 oldlb = oldlbs[
bound->index];
2229 oldub = oldubs[
bound->index];
2259 if( propdata->cutoffrow !=
NULL )
2331 if( nnonzduals !=
NULL )
2350 signx = (xs > xt) ? 1.0 : -1.0;
2357 side = scale * (xs/(xt-xs) - ys/(yt-ys));
2370 SCIPwarningMessage(
scip,
"Error while solving LP in quadratic constraint handler; LP solve terminated with" \
2371 "code <%d>\n", retstat);
2390 *xcoef = -signx - (mu * scale) / (xt - xs);
2391 *ycoef = (mu * scale) / (yt - ys);
2392 *constant = (*xcoef) * xval + (*ycoef) * yval;
2410 if( nnonzduals !=
NULL )
2468 assert(itlimit == -1 || itlimit >= 0);
2471 if( propdata->nbilinbounds <= 0 ||
SCIPgetDepth(
scip) != 0 || propdata->lastbilinidx >= propdata->nbilinbounds )
2474 SCIPdebugMsg(
scip,
"call applyObbtBilinear starting from %d\n", propdata->lastbilinidx);
2481 if( bilinearnlhdlr ==
NULL )
2514 && (nleftiterations > 0 || nleftiterations == -1)
2515 && (propdata->itlimitbilin < 0 || propdata->itlimitbilin > propdata->itusedbilin )
2522 bilinbound = propdata->bilinbounds[
i];
2525 SCIPdebugMsg(
scip,
"process %d: %s %s done=%u filtered=%d nunderest=%d noverest=%d\n",
i,
2540 for( k = 0; k < 4; ++k )
2542 CORNER corner = corners[k];
2560 if( (bilinbound->
filtered & corner) != 0 )
2572 SCIP_CALL(
solveBilinearLP(
scip,
x,
y, xs, ys, xt, yt, &xcoef, &ycoef, &constant, -1L,
2573 propdata->createlincons ? &nnonzduals :
NULL) );
2589 constant, &success) );
2595 SCIPdebugMsg(
scip,
" found %g x <= %g y + %g with violation %g\n", xcoef, ycoef, constant,
2596 (xcoef*xt - ycoef*yt - constant) / sqrt(
SQR(xcoef) +
SQR(ycoef) +
SQR(constant)));
2599 if( propdata->createlincons && nnonzduals > 1 )
2623 propdata->lastbilinidx =
i;
2630 if( propdata->cutoffrow !=
NULL )
2660 assert(maxnlcount >= nlcount + nindcount);
2669 counter += 0.5 * nindcount;
2671 counter += nindcount;
2705 unsigned int* nccounts
2787 for(
int i = 0;
i < nindconss; ++
i )
2802 for(
int v = 0; v < nconsvars; ++v )
2805 if( consvars[v] == slackvar )
2848 unsigned int* nccount;
2886 if( propdata->indicators )
2899 if( maxnlcount < (nlcount[
i] + nindcount[
i]) )
2900 maxnlcount = nlcount[
i] + nindcount[
i];
2904 propdata->boundssize = 2 *
nvars;
2910 smallub =
MIN(maxcouplingvalue, sepacouplingvalue);
2916 if(
varIsInteresting(
scip,
vars[
i], (propdata->onlynonconvexvars ? (
int)nccount[
i] : nlcount[
i]), (propdata->indicators ? nindcount[
i] : 0))
2917 &&
indicatorVarIsInteresting(
scip,
vars[
i], (propdata->onlynonconvexvars ? (
int)nccount[
i] : nlcount[
i]), (propdata->indicators ? nindcount[
i] : 0), propdata->indicatorthreshold) )
2922 bdaddress = &(propdata->bounds[bdidx]);
2925 propdata->bounds[bdidx]->var =
vars[
i];
2926 propdata->bounds[bdidx]->found =
FALSE;
2927 propdata->bounds[bdidx]->filtered =
FALSE;
2928 propdata->bounds[bdidx]->newval = 0.0;
2929 propdata->bounds[bdidx]->score =
getScore(
scip, propdata->bounds[bdidx], nlcount[
i], nindcount[
i], maxnlcount, smallub);
2930 propdata->bounds[bdidx]->done =
FALSE;
2931 propdata->bounds[bdidx]->nonconvex = (nccount[
i] > 0);
2932 propdata->bounds[bdidx]->indicator = (nindcount[
i] > 0);
2933 propdata->bounds[bdidx]->index = bdidx;
2937 bdaddress = &(propdata->bounds[bdidx]);
2940 propdata->bounds[bdidx]->var =
vars[
i];
2941 propdata->bounds[bdidx]->found =
FALSE;
2942 propdata->bounds[bdidx]->filtered =
FALSE;
2943 propdata->bounds[bdidx]->newval = 0.0;
2944 propdata->bounds[bdidx]->score =
getScore(
scip, propdata->bounds[bdidx], nlcount[
i], nindcount[
i], maxnlcount, smallub);
2945 propdata->bounds[bdidx]->done =
FALSE;
2946 propdata->bounds[bdidx]->nonconvex = (nccount[
i] > 0);
2947 propdata->bounds[bdidx]->indicator = (nindcount[
i] > 0);
2948 propdata->bounds[bdidx]->index = bdidx;
2954 propdata->nbounds = bdidx;
2959 if( propdata->nbounds > 0 && conshdlr !=
NULL && propdata->createbilinineqs )
2976 propdata->bilinboundssize = nexprs;
2977 propdata->nbilinbounds = 0;
2980 for(
i = 0;
i < nexprs; ++
i )
3001 bilinbound = propdata->bilinbounds[propdata->nbilinbounds];
3005 bilinbound->
expr = exprs[
i];
3012 ++(propdata->nbilinbounds);
3019 if( propdata->nbilinbounds > 1 )
3021 SCIPsortDownPtr((
void**) propdata->bilinbounds, compBilinboundsScore, propdata->nbilinbounds);
3034 if( propdata->nbounds <= 0 )
3036 assert(propdata->nbounds == 0);
3037 assert(propdata->boundssize >= 0 );
3043 if( propdata->nbounds > 0 )
3049 SCIPsortDownPtr((
void**) propdata->bounds, compBoundsScore, propdata->nbounds);
3091 propdata->bounds =
NULL;
3092 propdata->nbounds = -1;
3093 propdata->boundssize = 0;
3094 propdata->cutoffrow =
NULL;
3095 propdata->lastnode = -1;
3100 SCIPdebugMsg(
scip,
"creating genvbounds: %s\n", propdata->genvboundprop !=
NULL ?
"true" :
"false");
3139 SCIPdebugMsg(
scip,
"NLP not constructed and no indicator constraints available, skipping obbt\n");
3153 if( propdata->nbounds == -1 )
3166 assert(propdata->nbounds >= 0);
3170 if( propdata->nbounds <= 0 )
3194 if( propdata->itlimitfactor > 0.0 )
3196 propdata->minitlimit);
3205 if( propdata->createbilinineqs )
3208 if( propdata->itlimitbilin == 0L )
3211 propdata->itlimitbilin = (itlimit < 0 || propdata->itlimitfactorbilin < 0)
3212 ? -1L : (
SCIP_Longint)(itlimit * propdata->itlimitfactorbilin);
3250 propdata->randnumgen =
NULL;
3256 "FILTER-LP: %" SCIP_LONGINT_FORMAT " NGENVB(dive): %d NGENVB(aggr.): %d NGENVB(triv.) %d\n",
3257 propdata->nprobingiterations, propdata->nfiltered, propdata->ntrivialfiltered, propdata->nsolvedbounds,
3258 propdata->nfilterlpiters, propdata->ngenvboundsprobing, propdata->ngenvboundsaggrfil, propdata->ngenvboundstrivfil);
3261 if( propdata->bilinboundssize > 0 )
3263 for(
i = propdata->nbilinbounds - 1;
i >= 0; --
i )
3274 propdata->bilinboundssize = 0;
3275 propdata->nbilinbounds = 0;
3279 if( propdata->nbounds > 0 )
3282 for(
i = propdata->nbounds - 1;
i >= 0;
i-- )
3289 propdata->nbounds = -1;
3290 propdata->itlimitbilin = 0;
3291 propdata->itusedbilin = 0;
3332 propdata->nprobingiterations = 0;
3333 propdata->nfiltered = 0;
3334 propdata->ntrivialfiltered = 0;
3335 propdata->nsolvedbounds = 0;
3336 propdata->ngenvboundsprobing = 0;
3337 propdata->ngenvboundsaggrfil = 0;
3338 propdata->ngenvboundstrivfil = 0;
3339 propdata->nfilterlpiters = 0;
3340 propdata->lastidx = -1;
3341 propdata->propagatecounter = 0;
3342 propdata->npropagatedomreds = 0;
3346 propExecObbt, propdata) );
3355 "should obbt try to provide genvbounds if possible?",
3359 "should coefficients in filtering be normalized w.r.t. the domains sizes?",
3363 "try to filter bounds in so-called filter rounds by solving auxiliary LPs?",
3367 "try to filter bounds with the LP solution after each solve?",
3371 "should we try to generate genvbounds during trivial and aggressive filtering?",
3375 "try to create genvbounds during separation process?",
3379 "minimal number of filtered bounds to apply another filter round",
3383 "multiple of root node LP iterations used as total LP iteration limit for obbt (<= 0: no limit )",
3387 "multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit)",
3391 "minimum absolute value of nonconvex eigenvalues for a bilinear term",
3395 "minimum LP iteration limit",
3399 "feasibility tolerance for reduced costs used in obbt; this value is used if SCIP's dual feastol is greater",
3403 "maximum condition limit used in LP solver (-1.0: no limit)",
3407 "minimal relative improve for strengthening bounds",
3411 "threshold whether upper bounds of vars of indicator conss are considered or tightened",
3415 "only apply obbt on non-convex variables",
3419 "apply obbt on variables of indicator constraints? (independent of convexity)",
3423 "should integral bounds be tightened during the probing mode?",
3427 "should continuous bounds be tightened during the probing mode?",
3431 "solve auxiliary LPs in order to find valid inequalities for bilinear terms?",
3435 "create linear constraints from inequalities for bilinear terms?",
3439 "select the type of ordering algorithm which should be used (0: no special ordering, 1: greedy, 2: greedy reverse)",
3443 "should the obbt LP solution be separated?",
3447 "minimum number of iteration spend to separate an obbt LP solution",
3451 "maximum number of iteration spend to separate an obbt LP solution",
3455 "trigger a propagation round after that many bound tightenings (0: no propagation)",
constraint handler for indicator constraints
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIP_LONGINT_FORMAT
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetExprNLocksPosNonlinear(SCIP_EXPR *expr)
SCIP_HASHMAP * SCIPgetVarExprHashmapNonlinear(SCIP_CONSHDLR *conshdlr)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
unsigned int SCIPgetExprNSepaUsesActivityNonlinear(SCIP_EXPR *expr)
SCIP_VAR * SCIPgetSlackVarIndicator(SCIP_CONS *cons)
SCIP_CONS * SCIPgetLinearConsIndicator(SCIP_CONS *cons)
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)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
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)
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)
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)
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)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
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)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
SCIP_RETCODE SCIPincludePropObbt(SCIP *scip)
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPseparateSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool pretendroot, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
int SCIPgetNCuts(SCIP *scip)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
void SCIPcaptureExpr(SCIP_EXPR *expr)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
int SCIPgetNNLPVars(SCIP *scip)
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
SCIP_NLHDLR * SCIPfindNlhdlrNonlinear(SCIP_CONSHDLR *conshdlr, const char *name)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
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)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop,)
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop,)
const char * SCIPpropGetName(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop,)
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)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
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)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
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 SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeRandom(scip, &heurdata->randnumgen)
static SCIP_LPSOLSTAT lpsolstat
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemory(ptr)
#define BMSclearMemoryArray(ptr, num)
bilinear nonlinear handler
generalized variable bounds propagator
#define DEFAULT_ITLIMITFACTOR
static SCIP_Real getFilterCoef(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
#define GENVBOUND_PROP_NAME
static SCIP_VAR * bilinboundGetY(BILINBOUND *bilinbound)
#define DEFAULT_INDICATORS
#define DEFAULT_APPLY_FILTERROUNDS
#define DEFAULT_BOUNDSTREPS
#define DEFAULT_DUALFEASTOL
#define DEFAULT_SEPAMINITER
static SCIP_RETCODE filterExistingLP(SCIP *scip, SCIP_PROPDATA *propdata, int *nfiltered, BOUND *currbound)
#define DEFAULT_FILTERING_MIN
#define DEFAULT_MINNONCONVEXITY
#define DEFAULT_INDICATORTHRESHOLD
#define DEFAULT_SEPAMAXITER
static SCIP_Real bilinboundGetScore(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, BILINBOUND *bilinbound)
static SCIP_RETCODE initBounds(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_CONDITIONLIMIT
static int nextBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool convexphase)
static SCIP_RETCODE tightenBoundProbing(SCIP *scip, BOUND *bound, SCIP_Real newval, SCIP_Bool *tightened)
static SCIP_Real evalBound(SCIP *scip, BOUND *bound)
#define DEFAULT_TIGHTINTBOUNDSPROBING
static SCIP_Bool includeVarGenVBound(SCIP *scip, SCIP_VAR *var)
#define DEFAULT_MINITLIMIT
#define DEFAULT_PROPAGATEFREQ
static int bilinboundGetLocksNeg(BILINBOUND *bilinbound)
static SCIP_RETCODE filterBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit)
static SCIP_Bool indicatorVarIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount, int nindcount, SCIP_Real threshold)
#define DEFAULT_ORDERINGALGO
#define DEFAULT_GENVBDSDURINGSEPA
static SCIP_RETCODE addObjCutoff(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_APPLY_TRIVIALFITLERING
#define DEFAULT_SEPARATESOL
static SCIP_RETCODE solveLP(SCIP *scip, int itlimit, SCIP_Bool *error, SCIP_Bool *optimal)
#define DEFAULT_FILTERING_NORM
static void getCorners(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real *xt, SCIP_Real *yt)
static int getIterationsLeft(SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)
static SCIP_RETCODE filterRound(SCIP *scip, SCIP_PROPDATA *propdata, int itlimit, int *nfiltered, SCIP_Real *objcoefs, int *objcoefsinds, int nobjcoefs)
static SCIP_RETCODE sortBounds(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_CREATE_BILININEQS
#define DEFAULT_CREATE_LINCONS
#define DEFAULT_TIGHTCONTBOUNDSPROBING
struct BilinBound BILINBOUND
static SCIP_VAR * bilinboundGetX(BILINBOUND *bilinbound)
#define DEFAULT_CREATE_GENVBOUNDS
static SCIP_RETCODE setObjProbing(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Real coef)
static unsigned int getScore(SCIP *scip, BOUND *bound, int nlcount, int nindcount, int maxnlcount, SCIP_Real smallub)
#define DEFAULT_ITLIMITFAC_BILININEQS
#define DEFAULT_ONLYNONCONVEXVARS
static SCIP_RETCODE findNewBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)
static SCIP_Bool varIsFixedLocal(SCIP *scip, SCIP_VAR *var)
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)
static SCIP_RETCODE applyObbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
static SCIP_RETCODE applyObbtBilinear(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
#define DEFAULT_GENVBDSDURINGFILTER
static SCIP_RETCODE getNVarsIndicators(SCIP *scip, int *nindcount)
static SCIP_RETCODE createGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Bool *found)
static SCIP_RETCODE applyBoundChgs(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
static void getCorner(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *px, SCIP_Real *py)
static int bilinboundGetLocksPos(BILINBOUND *bilinbound)
static SCIP_RETCODE getNLPVarsNonConvexity(SCIP *scip, unsigned int *nccounts)
static SCIP_RETCODE applySeparation(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *currbound, SCIP_Longint *nleftiterations, SCIP_Bool *success)
static SCIP_Bool varIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount, int nindcount)
static void exchangeBounds(SCIP_PROPDATA *propdata, int i)
optimization-based bound tightening propagator
public methods for managing constraints
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
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
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
struct SCIP_Cons SCIP_CONS
struct SCIP_Conshdlr SCIP_CONSHDLR
struct SCIP_Expr SCIP_EXPR
enum SCIP_LPSolStat SCIP_LPSOLSTAT
enum SCIP_BoundType SCIP_BOUNDTYPE
@ SCIP_LPSOLSTAT_NOTSOLVED
@ SCIP_LPSOLSTAT_TIMELIMIT
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
@ SCIP_LPSOLSTAT_INFEASIBLE
@ SCIP_LPSOLSTAT_OBJLIMIT
@ SCIP_LPSOLSTAT_ITERLIMIT
enum SCIP_BaseStat SCIP_BASESTAT
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTPTRCOMP(x)
struct SCIP_RandNumGen SCIP_RANDNUMGEN
struct SCIP_Nlhdlr SCIP_NLHDLR
#define SCIP_DECL_PROPCOPY(x)
#define SCIP_DECL_PROPINITSOL(x)
#define SCIP_DECL_PROPFREE(x)
#define SCIP_DECL_PROPEXITSOL(x)
struct SCIP_Prop SCIP_PROP
#define SCIP_DECL_PROPRESPROP(x)
struct SCIP_PropData SCIP_PROPDATA
#define SCIP_DECL_PROPEXEC(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS