Detailed Description

nlobbt propagator

Author: Benjamin Mueller

Definition in file prop_nlobbt.c.

#include <assert.h>
#include "scip/prop_nlobbt.h"
#include "scip/prop_genvbounds.h"
#include "nlpi/nlpi.h"

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

Enumerations
enum	BoundStatus { UNSOLVED = 1, SOLVEDLB = 2, 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, 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 29 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ PROP_DESC

#define PROP_DESC "propagator template"

Definition at line 30 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ PROP_PRIORITY

#define PROP_PRIORITY -1100000

Definition at line 31 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ PROP_FREQ

#define PROP_FREQ -1

Definition at line 32 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ PROP_DELAY

#define PROP_DELAY TRUE

Definition at line 33 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 34 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 36 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 37 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ DEFAULT_FEASTOLFAC

#define DEFAULT_FEASTOLFAC 0.01

default factor for NLP feasibility tolerance

Definition at line 38 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 39 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ DEFAULT_ADDLPROWS

#define DEFAULT_ADDLPROWS TRUE

should (non-initial) LP rows be used?

Definition at line 40 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 41 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 44 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 45 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ DEFAULT_NLPVERLEVEL

#define DEFAULT_NLPVERLEVEL 0

verbosity level of NLP solver

Definition at line 46 of file prop_nlobbt.c.

Referenced by SCIPincludePropNlobbt().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 79

initial random seed

Definition at line 47 of file prop_nlobbt.c.

Referenced by SCIP_DECL_PROPINITSOL().

Enumeration Type Documentation

◆ BoundStatus

enum BoundStatus

status of bound candidates

Enumerator
UNSOLVED	did not solve LB or UB problem
SOLVEDLB	solved LB problem
SOLVEDUB	solved UB problem

Definition at line 54 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 98 of file prop_nlobbt.c.

References FALSE, isNlobbtApplicable(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPnlpiFreeProblem().

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

References filterCands(), SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Real, SCIPdebugMsg, SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), 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 183 of file prop_nlobbt.c.

References addGenVBound(), SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisLE(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), 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 241 of file prop_nlobbt.c.

References REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgenVBoundAdd(), SCIPisFeasGT(), SCIPisFeasZero(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), 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,
		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?
nlpiter	buffer to store the total number of nlp iterations
result	pointer to store result

Definition at line 318 of file prop_nlobbt.c.

References addGenVBound(), applyNlobbt(), FALSE, filterCands(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_TILIM, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPnlpiChgVarBounds(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiGetStatistics(), SCIPnlpiSetIntPar(), SCIPnlpiSetObjective(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlpStatisticsGetNIterations(), SCIPnlpStatisticsGetTotalTime(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

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

References FALSE, isNlobbtApplicable(), propdataClear(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPFREE(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_RELOBJTOL, SCIP_NLPPAR_VERBLEVEL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddNlpiProbRows(), SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcreateNlpiProb(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPfeastol(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPRows(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNRootLPIterations(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisFeasEQ(), SCIPisGT(), SCIPisStopped(), SCIPnlpiCreateProblem(), SCIPnlpiSetIntPar(), SCIPnlpiSetRealPar(), SCIPrandomGetReal(), SCIPsortDownRealIntPtr(), SCIPupdateNlpiProb(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbLocal(), SOLVEDLB, SOLVEDUB, solveNlp(), TRUE, and UNSOLVED.

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

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

References DEFAULT_RANDSEED, SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_OKAY, SCIPblkmem(), SCIPcreateRandom(), SCIPfindProp(), SCIPnlpStatisticsCreate(), and SCIPpropGetData().

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

References propdataClear(), SCIP_CALL, SCIP_DECL_PROPEXEC(), SCIP_OKAY, SCIPblkmem(), SCIPfreeRandom(), SCIPnlpStatisticsFree(), and SCIPpropGetData().

Referenced by SCIP_DECL_PROPINITSOL().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecNlobbt )

static

execution method of propagator

Definition at line 652 of file prop_nlobbt.c.

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

Referenced by SCIP_DECL_PROPEXITSOL().

SCIP

Detailed Description

Macros

Enumerations

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

Enumeration Type Documentation

◆ BoundStatus

Function Documentation

◆ propdataClear()

◆ isNlobbtApplicable()

◆ filterCands()

◆ addGenVBound()

◆ solveNlp()

◆ applyNlobbt()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPEXITSOL()

◆ SCIP_DECL_PROPEXEC()