Scippy

SCIP

Solving Constraint Integer Programs

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
scipSCIP data structure
propdatapropagator 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
scipSCIP data structure
propdatapropagation 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
scipSCIP data structure
propdatapropagator 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
scipSCIP data structure
propdatapropagator data
varvariable used in last NLP solve
varidxvariable index in the propdata->nlpivars array
boundtypetype of bound provided by the genvbound
cutoffboundcutoff 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
scipSCIP data structure
propdatapropagator data
varvariable to propagate
varidxvariable index in the propdata->nlpivars array
boundtypeminimize or maximize var?
nlpparamNLP solve parameters
nlpiterbuffer to store the total number of nlp iterations
resultpointer 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
scipSCIP data structure
propdatapropagation data
resultpointer 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()