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.

◆ PROP_DESC

#define PROP_DESC "propagator template"

Definition at line 62 of file prop_nlobbt.c.

◆ PROP_PRIORITY

#define PROP_PRIORITY -1100000

Definition at line 63 of file prop_nlobbt.c.

◆ PROP_FREQ

#define PROP_FREQ -1

Definition at line 64 of file prop_nlobbt.c.

◆ PROP_DELAY

#define PROP_DELAY TRUE

Definition at line 65 of file prop_nlobbt.c.

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 66 of file prop_nlobbt.c.

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

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

◆ DEFAULT_FEASTOLFAC

#define DEFAULT_FEASTOLFAC 0.01

default factor for NLP feasibility tolerance

Definition at line 70 of file prop_nlobbt.c.

◆ DEFAULT_RELOBJTOLFAC

#define DEFAULT_RELOBJTOLFAC 0.01

default factor for NLP relative objective tolerance

Definition at line 71 of file prop_nlobbt.c.

◆ DEFAULT_ADDLPROWS

#define DEFAULT_ADDLPROWS TRUE

should (non-initial) LP rows be used?

Definition at line 72 of file prop_nlobbt.c.

◆ 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 74 of file prop_nlobbt.c.

◆ DEFAULT_NLPITERLIMIT

#define DEFAULT_NLPITERLIMIT 500

default iteration limit of NLP solver; 0 for no limit

Definition at line 75 of file prop_nlobbt.c.

◆ DEFAULT_NLPTIMELIMIT

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

◆ DEFAULT_NLPVERLEVEL

#define DEFAULT_NLPVERLEVEL 0

verbosity level of NLP solver

Definition at line 77 of file prop_nlobbt.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 79

initial random seed

Definition at line 78 of file prop_nlobbt.c.

◆ UNSOLVED

#define UNSOLVED 1

did not solve LB or UB problem

Definition at line 85 of file prop_nlobbt.c.

◆ SOLVEDLB

#define SOLVEDLB 2

solved LB problem

Definition at line 86 of file prop_nlobbt.c.

◆ SOLVEDUB

#define SOLVEDUB 4

solved UB problem

Definition at line 87 of file prop_nlobbt.c.

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 125 of file prop_nlobbt.c.

References FALSE, NULL, 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 155 of file prop_nlobbt.c.

References NULL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Real, SCIPdebugMsg, SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), and SCIPnlrowGetRhs().

Referenced by applyNlobbt().

◆ 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 210 of file prop_nlobbt.c.

References 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 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 268 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(), and SCIPvarGetName().

Referenced by 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 345 of file prop_nlobbt.c.

References addGenVBound(), 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(), and SCIP_NlpParam::timelimit.

Referenced by 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 473 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_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().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeNlobbt )

static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 621 of file prop_nlobbt.c.

References NULL, propdataClear(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ 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 637 of file prop_nlobbt.c.

References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfindProp(), SCIPpropGetData(), and TRUE.

◆ 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 659 of file prop_nlobbt.c.

References NULL, propdataClear(), SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpropGetData().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecNlobbt )

static

execution method of propagator

Definition at line 675 of file prop_nlobbt.c.

References applyNlobbt(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallColsInLP(), SCIPallowWeakDualReds(), SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetNNlpis(), SCIPgetStage(), SCIPinDive(), SCIPinProbing(), SCIPinRepropagation(), SCIPisNLPConstructed(), SCIPnodeGetNumber(), and SCIPpropGetData().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ PROP_TIMING

◆ DEFAULT_MINNONCONVEXFRAC

◆ DEFAULT_MINLINEARFRAC

◆ DEFAULT_FEASTOLFAC

◆ DEFAULT_RELOBJTOLFAC

◆ DEFAULT_ADDLPROWS

◆ DEFAULT_ITLIMITFACTOR

◆ DEFAULT_NLPITERLIMIT

◆ DEFAULT_NLPTIMELIMIT

◆ DEFAULT_NLPVERLEVEL

◆ DEFAULT_RANDSEED

◆ UNSOLVED

◆ SOLVEDLB

◆ SOLVEDUB

Function Documentation

◆ propdataClear()

◆ isNlobbtApplicable()

◆ filterCands()

◆ addGenVBound()

◆ solveNlp()

◆ applyNlobbt()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPEXITSOL()

◆ SCIP_DECL_PROPEXEC()