prop_nlobbt.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
60 #define DEFAULT_MINNONCONVEXFRAC 0.20 /**< default minimum (# convex nlrows)/(# nonconvex nlrows) threshold to apply propagator */
61 #define DEFAULT_MINLINEARFRAC 0.02 /**< default minimum (# convex nlrows)/(# linear nlrows) threshold to apply propagator */
65 #define DEFAULT_ITLIMITFACTOR 2.0 /**< multiple of root node LP iterations used as total LP iteration
78 {
82 };
108 SCIP_Real minnonconvexfrac; /**< minimum (#convex nlrows)/(#nonconvex nlrows) threshold to apply propagator */
109 SCIP_Real minlinearfrac; /**< minimum (#convex nlrows)/(#linear nlrows) threshold to apply propagator */
196 SCIPdebugMsg(scip, "nconvex=%d nnonconvex=%d nlinear=%d\n", nconvexnlrows, nnonconvexnlrows, nlinearnlrows);
217 SCIP_CALL( SCIPnlpiGetSolution(propdata->nlpi, propdata->nlpiprob, &primal, NULL, NULL, NULL, NULL) );
220 /* we skip all candidates which have been processed already, i.e., starting at propdata->currpos + 1 */
241 SCIPdebugMsg(scip, "filter LB of %s in [%g,%g] with %g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var),
250 SCIPdebugMsg(scip, "filter UB of %s in [%g,%g] with %g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var),
260 /** tries to add a generalized variable bound by exploiting the dual solution of the last NLP solve (see @ref
289 SCIP_CALL( SCIPnlpiGetSolution(propdata->nlpi, propdata->nlpiprob, &primal, &dual, &alpha, &beta, NULL) );
291 /* not possible to generate genvbound if the duals for the propagated variable do not disappear */
324 SCIP_CALL( SCIPgenVBoundAdd(scip, propdata->genvboundprop, lvbvars, var, lvbcoefs, nlvbvars, -mu, constant,
335 /** sets the objective function, solves the NLP, and tightens the given variable; after calling this function, the
384 SCIP_CALL( SCIPnlpiSetRealPar(propdata->nlpi, propdata->nlpiprob, SCIP_NLPPAR_TILIM, timelimit) );
385 SCIP_CALL( SCIPnlpiSetIntPar(propdata->nlpi, propdata->nlpiprob, SCIP_NLPPAR_ITLIM, iterlimit) );
389 SCIP_CALL( SCIPnlpiSetObjective(propdata->nlpi, propdata->nlpiprob, 1, &varidx, &obj, 0, NULL, NULL, NULL, 0.0) );
394 SCIPdebugMsg(scip, "NLP solstat = %d\n", SCIPnlpiGetSolstat(propdata->nlpi, propdata->nlpiprob));
398 SCIP_CALL( SCIPnlpiGetStatistics(propdata->nlpi, propdata->nlpiprob, propdata->nlpstatistics) );
400 SCIPdebugMsg(scip, "iterations %d time %g\n", *nlpiter, SCIPnlpStatisticsGetTotalTime(propdata->nlpstatistics));
402 /* filter bound candidates first, otherwise we do not have access to the primal solution values */
420 SCIP_CALL( SCIPnlpiGetSolution(propdata->nlpi, propdata->nlpiprob, &primal, NULL, NULL, NULL, NULL) );
449 SCIPdebugMsg(scip, "tightened bounds of %s from [%g,%g] to [%g,%g]\n", SCIPvarGetName(var), oldlb, oldub, lb, ub);
456 SCIP_CALL( SCIPnlpiSetObjective(propdata->nlpi, propdata->nlpiprob, 1, &varidx, &obj, 0, NULL, NULL, NULL, 0.0) );
464 * binary and variables with a small domain will be ignored to reduce the computational cost of the propagator; after
465 * solving each NLP we filter out all variable candidates which are on their lower or upper bound; candidates with a
517 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &propdata->nlpivars, SCIPgetVars(scip), propdata->nlpinvars) ); /*lint !e666*/
521 SCIP_CALL( SCIPcreateNlpiProb(scip, propdata->nlpi, SCIPgetNLPNlRows(scip), SCIPgetNNLPNlRows(scip),
522 propdata->nlpiprob, propdata->var2nlpiidx, NULL, propdata->nlscore, SCIPgetCutoffbound(scip), FALSE, TRUE) );
524 /* initialize bound status; perturb nlscores by a factor which ensures that zero scores remain zero */
529 propdata->nlscore[i] *= 1.0 + SCIPrandomGetReal(propdata->randnumgen, SCIPfeastol(scip), 2.0 * SCIPfeastol(scip));
553 SCIPsortDownRealIntPtr(propdata->nlscore, propdata->status, (void**)propdata->nlpivars, propdata->nlpinvars);
561 SCIP_CALL( SCIPnlpiSetIntPar(propdata->nlpi, propdata->nlpiprob, SCIP_NLPPAR_VERBLEVEL, propdata->nlpverblevel) );
600 if( *result != SCIP_CUTOFF && (propdata->status[propdata->currpos] & SOLVEDUB) == 0 ) /*lint !e641*/
633 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
656 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
685 || SCIPinProbing(scip) || SCIPinDive(scip) || !SCIPallowWeakDualReds(scip) || SCIPgetNNlpis(scip) == 0 )
737 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
755 &propdata->minnonconvexfrac, TRUE, DEFAULT_MINNONCONVEXFRAC, 0.0, SCIPinfinity(scip), NULL, NULL) );
Definition: type_nlpi.h:46
Definition: type_result.h:33
public methods for SCIP parameter handling
public methods for branch and bound tree
Definition: type_nlpi.h:51
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_scip.h:59
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5184
public methods for memory management
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5301
static SCIP_RETCODE addGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int varidx, SCIP_BOUNDTYPE boundtype, SCIP_Real cutoffbound)
Definition: prop_nlobbt.c:265
public methods for timing
Definition: struct_var.h:198
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
Definition: nlpi.c:212
SCIP_RETCODE SCIPnlpiChgVarBounds(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nvars, const int *indices, const SCIP_Real *lbs, const SCIP_Real *ubs)
Definition: nlpi.c:326
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9967
Definition: type_var.h:53
Definition: struct_misc.h:259
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
public methods for problem variables
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
Definition: type_expr.h:87
Definition: type_nlpi.h:47
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: nlpi.c:672
public methods for SCIP variables
static SCIP_RETCODE propdataClear(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_nlobbt.c:122
public methods for numerical tolerances
SCIP_RETCODE SCIPnlpiSetObjective(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nlins, const int *lininds, const SCIP_Real *linvals, int nquadelems, const SCIP_QUADELEM *quadelems, const int *exprvaridxs, const SCIP_EXPRTREE *exprtree, const SCIP_Real constant)
Definition: nlpi.c:301
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
public methods for querying solving statistics
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3220
public methods for the branch-and-bound tree
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
Definition: struct_misc.h:128
SCIP_RETCODE SCIPnlpiGetStatistics(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:557
void SCIPnlpStatisticsFree(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:803
Definition: type_nlpi.h:63
Definition: type_result.h:35
Definition: type_nlpi.h:52
Definition: struct_nlpi.h:78
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues, SCIP_Real *objval)
Definition: nlpi.c:538
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
static SCIP_RETCODE applyNlobbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
Definition: prop_nlobbt.c:470
public methods for nonlinear functions
Definition: type_lp.h:47
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:512
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
Definition: scip_nonlinear.c:959
Definition: type_retcode.h:33
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
Definition: type_result.h:42
static SCIP_RETCODE solveNlp(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int varidx, SCIP_BOUNDTYPE boundtype, int *nlpiter, SCIP_RESULT *result)
Definition: prop_nlobbt.c:342
Definition: struct_prop.h:37
public methods for NLP management
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
public data structures and miscellaneous methods
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
int SCIPnlpStatisticsGetNIterations(SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:818
nonlinear OBBT propagator
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
Definition: nlpi.c:637
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:498
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
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
public methods for the LP relaxation, rows and columns
public methods for nonlinear relaxations
methods for sorting joint arrays of various types
SCIP_Real SCIPnlpStatisticsGetTotalTime(SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:828
Definition: type_nlpi.h:48
general public methods
SCIP_EXPORT void SCIPsortDownRealIntPtr(SCIP_Real *realarray, int *intarray, void **ptrarray, int len)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
static SCIP_RETCODE filterCands(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_nlobbt.c:207
SCIP_RETCODE SCIPupdateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
Definition: scip_nonlinear.c:1290
public methods for random numbers
Definition: type_lp.h:48
Definition: type_expr.h:86
public methods for the probing mode
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
Definition: nlpi.c:225
public methods for message output
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:479
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
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: struct_nlp.h:63
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
Definition: prop_nlobbt.c:82
Definition: prop_nlobbt.c:80
public methods for propagator plugins
Definition: type_set.h:44
Definition: type_nlpi.h:62
SCIP_RETCODE SCIPnlpStatisticsCreate(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:786
Definition: prop_nlobbt.c:81
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
Definition: objbenders.h:33
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
public methods for global and local (sub)problems
Definition: nlpi_all.c:47
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip_nonlinear.c:1342
static SCIP_Bool isNlobbtApplicable(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_nlobbt.c:152
Definition: type_result.h:39
public methods for propagators
generalized variable bounds propagator
memory allocation routines
Definition: struct_nlpi.h:35