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) |
#define PROP_NAME "nlobbt" |
Definition at line 61 of file prop_nlobbt.c.
#define PROP_DESC "propagator template" |
Definition at line 62 of file prop_nlobbt.c.
#define PROP_PRIORITY -1100000 |
Definition at line 63 of file prop_nlobbt.c.
#define PROP_FREQ -1 |
Definition at line 64 of file prop_nlobbt.c.
#define PROP_DELAY TRUE |
Definition at line 65 of file prop_nlobbt.c.
#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 66 of file prop_nlobbt.c.
#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().
#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().
#define DEFAULT_FEASTOLFAC 0.01 |
default factor for NLP feasibility tolerance
Definition at line 70 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
#define DEFAULT_RELOBJTOLFAC 0.01 |
default factor for NLP relative objective tolerance
Definition at line 71 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
#define DEFAULT_ADDLPROWS TRUE |
should (non-initial) LP rows be used?
Definition at line 72 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
#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(), and SCIPincludePropObbt().
#define DEFAULT_NLPITERLIMIT 500 |
default iteration limit of NLP solver; 0 for no limit
Definition at line 75 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
#define DEFAULT_NLPTIMELIMIT 0.0 |
default time limit of NLP solver; 0.0 for no limit
Definition at line 76 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
#define DEFAULT_NLPVERLEVEL 0 |
verbosity level of NLP solver
Definition at line 77 of file prop_nlobbt.c.
Referenced by SCIPincludePropNlobbt().
#define DEFAULT_RANDSEED 79 |
initial random seed
Definition at line 78 of file prop_nlobbt.c.
#define UNSOLVED 1 |
did not solve LB or UB problem
Definition at line 85 of file prop_nlobbt.c.
Referenced by applyNlobbt().
#define SOLVEDLB 2 |
solved LB problem
Definition at line 86 of file prop_nlobbt.c.
Referenced by applyNlobbt(), and filterCands().
#define SOLVEDUB 4 |
solved UB problem
Definition at line 87 of file prop_nlobbt.c.
Referenced by applyNlobbt(), and filterCands().
|
static |
clears the propagator data
scip | SCIP data structure |
propdata | propagator data |
Definition at line 125 of file prop_nlobbt.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPhashmapFree().
Referenced by applyNlobbt(), SCIP_DECL_PROPEXITSOL(), and SCIP_DECL_PROPFREE().
|
static |
checks whether it is worth to call nonlinear OBBT procedure
scip | SCIP data structure |
propdata | propagation data |
Definition at line 155 of file prop_nlobbt.c.
References i, NULL, SCIP_Bool, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Real, SCIPdebugMsg, SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), and SCIPnlrowGetRhs().
Referenced by applyNlobbt().
|
static |
filters variables which achieve their lower or dual bound in the current NLP solution
scip | SCIP data structure |
propdata | propagator data |
Definition at line 210 of file prop_nlobbt.c.
References assert(), i, NULL, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisLE(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SOLVEDLB, SOLVEDUB, var, and varidx.
Referenced by solveNlp().
|
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)
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 268 of file prop_nlobbt.c.
References alpha, assert(), i, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgenVBoundAdd(), SCIPisFeasGT(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetName(), var, and varidx.
Referenced by 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
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 345 of file prop_nlobbt.c.
References addGenVBound(), assert(), FALSE, filterCands(), SCIP_NlpParam::iterlimit, MIN, NULL, obj, result, 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, var, and varidx.
Referenced by 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
scip | SCIP data structure |
propdata | propagation data |
result | pointer to store result |
Definition at line 473 of file prop_nlobbt.c.
References assert(), FALSE, SCIP_NlpParam::feastol, i, isNlobbtApplicable(), NULL, SCIP_NlpParam::opttol, propdataClear(), result, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, 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, var, varidx, and SCIP_NlpParam::verblevel.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 621 of file prop_nlobbt.c.
References assert(), NULL, propdataClear(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 637 of file prop_nlobbt.c.
References assert(), DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfindProp(), SCIPpropGetData(), and TRUE.
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 659 of file prop_nlobbt.c.
References assert(), NULL, propdataClear(), SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpropGetData().
|
static |
execution method of propagator
Definition at line 675 of file prop_nlobbt.c.
References applyNlobbt(), assert(), NULL, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallColsInLP(), SCIPallowWeakDualReds(), SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetNNlpis(), SCIPgetStage(), SCIPinDive(), SCIPinProbing(), SCIPinRepropagation(), SCIPisNLPConstructed(), SCIPnodeGetNumber(), and SCIPpropGetData().