prop_nlobbt.c File Reference

Detailed Description

nlobbt propagator

Author

Benjamin Mueller

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 SCIP_RETCODE propdataClear ( SCIP *  scip, SCIP_PROPDATA *  propdata  )

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 SCIP_Bool isNlobbtApplicable ( SCIP *  scip, SCIP_PROPDATA *  propdata  )

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 SCIP_RETCODE filterCands ( SCIP *  scip, SCIP_PROPDATA *  propdata  )

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 SCIP_RETCODE addGenVBound ( SCIP *  scip, SCIP_PROPDATA *  propdata, SCIP_VAR *  var, int  varidx, SCIP_BOUNDTYPE  boundtype, SCIP_Real  cutoffbound  )

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 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

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, MIN, 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 SCIP_RETCODE applyNlobbt ( SCIP *  scip, SCIP_PROPDATA *  propdata, SCIP_RESULT *  result  )

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 SCIP_DECL_PROPFREE ( propFreeNlobbt  )

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 SCIP_DECL_PROPINITSOL ( propInitsolNlobbt  )

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 SCIP_DECL_PROPEXITSOL ( propExitsolNlobbt  )

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 SCIP_DECL_PROPEXEC ( propExecNlobbt  )

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().