Detailed Description
nlobbt propagator
Definition in file prop_nlobbt.c.
#include "blockmemshell/memory.h"
#include "scip/prop_genvbounds.h"
#include "scip/prop_nlobbt.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_nlp.h"
#include "scip/pub_prop.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_nlpi.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_prop.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | PROP_NAME "nlobbt" |
#define | PROP_DESC "propagator template" |
#define | PROP_PRIORITY -1100000 |
#define | PROP_FREQ -1 |
#define | PROP_DELAY TRUE |
#define | PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP |
#define | DEFAULT_MINNONCONVEXFRAC 0.20 |
#define | DEFAULT_MINLINEARFRAC 0.02 |
#define | DEFAULT_FEASTOLFAC 0.01 |
#define | DEFAULT_RELOBJTOLFAC 0.01 |
#define | DEFAULT_ADDLPROWS TRUE |
#define | DEFAULT_ITLIMITFACTOR 2.0 |
#define | DEFAULT_NLPITERLIMIT 500 |
#define | DEFAULT_NLPTIMELIMIT 0.0 |
#define | DEFAULT_NLPVERLEVEL 0 |
#define | DEFAULT_RANDSEED 79 |
#define | UNSOLVED 1 |
#define | SOLVEDLB 2 |
#define | SOLVEDUB 4 |
Functions | |
static SCIP_RETCODE | propdataClear (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_Bool | isNlobbtApplicable (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | filterCands (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | addGenVBound (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int varidx, SCIP_BOUNDTYPE boundtype, SCIP_Real cutoffbound) |
static SCIP_RETCODE | solveNlp (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int varidx, SCIP_BOUNDTYPE boundtype, SCIP_NLPPARAM *nlpparam, int *nlpiter, SCIP_RESULT *result) |
static SCIP_RETCODE | applyNlobbt (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result) |
static | SCIP_DECL_PROPFREE (propFreeNlobbt) |
static | SCIP_DECL_PROPINITSOL (propInitsolNlobbt) |
static | SCIP_DECL_PROPEXITSOL (propExitsolNlobbt) |
static | SCIP_DECL_PROPEXEC (propExecNlobbt) |
SCIP_RETCODE | SCIPincludePropNlobbt (SCIP *scip) |
Macro Definition Documentation
◆ PROP_NAME
#define PROP_NAME "nlobbt" |
Definition at line 61 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ PROP_DESC
#define PROP_DESC "propagator template" |
Definition at line 62 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ PROP_PRIORITY
#define PROP_PRIORITY -1100000 |
Definition at line 63 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ PROP_FREQ
#define PROP_FREQ -1 |
Definition at line 64 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ PROP_DELAY
#define PROP_DELAY TRUE |
Definition at line 65 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ PROP_TIMING
#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 66 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_MINNONCONVEXFRAC
#define DEFAULT_MINNONCONVEXFRAC 0.20 |
default minimum (# convex nlrows)/(# nonconvex nlrows) threshold to apply propagator
Definition at line 68 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_MINLINEARFRAC
#define DEFAULT_MINLINEARFRAC 0.02 |
default minimum (# convex nlrows)/(# linear nlrows) threshold to apply propagator
Definition at line 69 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_FEASTOLFAC
#define DEFAULT_FEASTOLFAC 0.01 |
default factor for NLP feasibility tolerance
Definition at line 70 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_RELOBJTOLFAC
#define DEFAULT_RELOBJTOLFAC 0.01 |
default factor for NLP relative objective tolerance
Definition at line 71 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_ADDLPROWS
#define DEFAULT_ADDLPROWS TRUE |
should (non-initial) LP rows be used?
Definition at line 72 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_ITLIMITFACTOR
#define DEFAULT_ITLIMITFACTOR 2.0 |
multiple of root node LP iterations used as total LP iteration limit for nlobbt (<= 0: no limit )
Definition at line 73 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_NLPITERLIMIT
#define DEFAULT_NLPITERLIMIT 500 |
default iteration limit of NLP solver; 0 for no limit
Definition at line 76 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_NLPTIMELIMIT
#define DEFAULT_NLPTIMELIMIT 0.0 |
default time limit of NLP solver; 0.0 for no limit
Definition at line 77 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_NLPVERLEVEL
#define DEFAULT_NLPVERLEVEL 0 |
verbosity level of NLP solver
Definition at line 78 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 79 |
initial random seed
Definition at line 79 of file prop_nlobbt.c.
Referenced by SCIP_DECL_PROPINITSOL().
◆ UNSOLVED
#define UNSOLVED 1 |
did not solve LB or UB problem
Definition at line 86 of file prop_nlobbt.c.
Referenced by applyNlobbt().
◆ SOLVEDLB
#define SOLVEDLB 2 |
solved LB problem
Definition at line 87 of file prop_nlobbt.c.
Referenced by applyNlobbt(), and filterCands().
◆ SOLVEDUB
#define SOLVEDUB 4 |
solved UB problem
Definition at line 88 of file prop_nlobbt.c.
Referenced by applyNlobbt(), and filterCands().
Function Documentation
◆ propdataClear()
|
static |
clears the propagator data
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 126 of file prop_nlobbt.c.
References FALSE, isNlobbtApplicable(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPhashmapFree().
Referenced by applyNlobbt(), SCIP_DECL_PROPEXITSOL(), and SCIP_DECL_PROPFREE().
◆ isNlobbtApplicable()
|
static |
checks whether it is worth to call nonlinear OBBT procedure
- Parameters
-
scip SCIP data structure propdata propagation data
Definition at line 156 of file prop_nlobbt.c.
References filterCands(), NULL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Real, SCIPdebugMsg, SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), and SCIPnlrowGetRhs().
Referenced by applyNlobbt(), and propdataClear().
◆ filterCands()
|
static |
filters variables which achieve their lower or dual bound in the current NLP solution
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 211 of file prop_nlobbt.c.
References addGenVBound(), NULL, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisLE(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SOLVEDLB, and SOLVEDUB.
Referenced by isNlobbtApplicable(), and solveNlp().
◆ addGenVBound()
|
static |
tries to add a generalized variable bound by exploiting the dual solution of the last NLP solve (see prop_nlobbt.h for more information)
- Parameters
-
scip SCIP data structure propdata propagator data var variable used in last NLP solve varidx variable index in the propdata->nlpivars array boundtype type of bound provided by the genvbound cutoffbound cutoff bound
Definition at line 269 of file prop_nlobbt.c.
References NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgenVBoundAdd(), SCIPisFeasGT(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetName(), and solveNlp().
Referenced by filterCands(), and solveNlp().
◆ solveNlp()
|
static |
sets the objective function, solves the NLP, and tightens the given variable; after calling this function, the objective function is set to zero
- Note
- function assumes that objective function is zero
- Parameters
-
scip SCIP data structure propdata propagator data var variable to propagate varidx variable index in the propdata->nlpivars array boundtype minimize or maximize var? nlpparam NLP solve parameters nlpiter buffer to store the total number of nlp iterations result pointer to store result
Definition at line 346 of file prop_nlobbt.c.
References addGenVBound(), applyNlobbt(), FALSE, filterCands(), SCIP_NlpParam::iterlimit, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIP_NlpParam::timelimit, and Scip::totaltime.
Referenced by addGenVBound(), and applyNlobbt().
◆ applyNlobbt()
|
static |
main method of the propagator
creates a convex NLP relaxation and solves the OBBT-NLPs for each possible candidate; binary and variables with a small domain will be ignored to reduce the computational cost of the propagator; after solving each NLP we filter out all variable candidates which are on their lower or upper bound; candidates with a larger number of occurrences are preferred
- Parameters
-
scip SCIP data structure propdata propagation data result pointer to store result
Definition at line 474 of file prop_nlobbt.c.
References FALSE, SCIP_NlpParam::feastol, isNlobbtApplicable(), NULL, SCIP_NlpParam::opttol, propdataClear(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPFREE(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_NLPPARAM_DEFAULT, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddNlpiProblemRows(), SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcreateNlpiProblemFromNlRows(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPfeastol(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPRows(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNRootLPIterations(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisFeasEQ(), SCIPisGT(), SCIPisStopped(), SCIPrandomGetReal(), SCIPsortDownRealIntPtr(), SCIPupdateNlpiProblem(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbLocal(), SOLVEDLB, SOLVEDUB, solveNlp(), TRUE, UNSOLVED, and SCIP_NlpParam::verblevel.
Referenced by SCIP_DECL_PROPEXEC(), and solveNlp().
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 622 of file prop_nlobbt.c.
References NULL, propdataClear(), SCIP_CALL, SCIP_DECL_PROPINITSOL(), SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().
Referenced by applyNlobbt().
◆ SCIP_DECL_PROPINITSOL()
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 638 of file prop_nlobbt.c.
References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_OKAY, SCIPcreateRandom(), SCIPfindProp(), SCIPpropGetData(), and TRUE.
Referenced by SCIP_DECL_PROPFREE().
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 660 of file prop_nlobbt.c.
References NULL, propdataClear(), SCIP_CALL, SCIP_DECL_PROPEXEC(), SCIP_OKAY, SCIPfreeRandom(), and SCIPpropGetData().
Referenced by SCIP_DECL_PROPINITSOL().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 676 of file prop_nlobbt.c.
References applyNlobbt(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallColsInLP(), SCIPallowWeakDualReds(), SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetNNlpis(), SCIPgetStage(), SCIPincludePropNlobbt(), SCIPinDive(), SCIPinProbing(), SCIPinRepropagation(), SCIPisNLPConstructed(), SCIPnodeGetNumber(), and SCIPpropGetData().
Referenced by SCIP_DECL_PROPEXITSOL().