heur_dualval.c File Reference

Detailed Description

dualval primal heuristic

Author

Tobias Buchwald

This heuristic tries to find solutions by taking the LP or NLP, rounding solution values, fixing the variables to the rounded values and then changing some of the values.To determine which variable is changed we give each variable a ranking dependent on its dualvalue. We work with a transformed problem that is always feasible and has objective = 0 iff the original problem is also feasible. Thus we cannot expect to find really good solutions.

Definition in file heur_dualval.c.

#include <assert.h>
#include "scip/heur_dualval.h"
#include "scip/scip.h"
#include "scip/cons_linear.h"
#include "scip/cons_indicator.h"
#include "scip/cons_varbound.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/cons_knapsack.h"
#include "nlpi/nlpi.h"
#include "nlpi/nlpioracle.h"
#include "nlpi/nlpi_ipopt.h"
#include "nlpi/exprinterpret.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME   "dualval"
#define	HEUR_DESC   "primal heuristic using dual values"
#define	HEUR_DISPCHAR   'Y'
#define	HEUR_PRIORITY   0
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
#define	HEUR_USESSUBSCIP   TRUE
#define	EVENTHDLR_NAME   "lpsol_dualval"
#define	EVENTHDLR_DESC   "event handler for lp solution found"
#define	DEFAULT_FORCEIMPROVEMENTS   FALSE
#define	DEFAULT_ONLYCHEAPER   TRUE
#define	DEFAULT_ONLYLEAVES   FALSE
#define	DEFAULT_RELAXINDICATORS   FALSE
#define	DEFAULT_RELAXCONTVARS   FALSE
#define	DEFAULT_HEURVERBLEVEL   0
#define	DEFAULT_NLPVERBLEVEL   0
#define	DEFAULT_RANKVALUE   10
#define	DEFAULT_MAXCALLS   25
#define	DEFAULT_DYNAMICDEPTH   0
#define	DEFAULT_MAXEQUALRANKS   50
#define	DEFAULT_MINGAP   5.0
#define	DEFAULT_LAMBDASLACK   1.0
#define	DEFAULT_LAMBDAOBJ   0.0
#define	BIG_VALUE   1E+10

Functions
static	SCIP_DECL_EVENTINIT (eventInitLPsol)
static	SCIP_DECL_EVENTEXIT (eventExitLPsol)
static	SCIP_DECL_EVENTEXEC (eventExecLPsol)
static SCIP_RETCODE	SCIPincludeEventHdlrLPsol (SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	releaseHashmapEntries (SCIP *scip, SCIP_HASHMAP *hashmap, SCIP_Bool isvarmap)
static SCIP_RETCODE	releaseHashmapNLPRows (SCIP *scip, SCIP_HASHMAP *hashmap)
static SCIP_RETCODE	addLinearConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	addVarboundConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	addLogicOrConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	addSetppcConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	addKnapsackConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	addLinearConstraintsToNlp (SCIP *scip, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	createSolFromSubScipSol (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol, SCIP_SOL *subsol)
static SCIP_RETCODE	createSubSCIP (SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	freeSubSCIP (SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	createSolFromNLP (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol)
static SCIP_RETCODE	fixDiscreteVars (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *refpoint, SCIP_SOL **transsol)
static SCIP_RETCODE	freeMemory (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *transsol, SCIP_Real *absranks, SCIP_Real *ranks, SCIP_VAR **sortedvars, SCIP_Bool beforeswitching, SCIP_Bool clearswitchedvars)
static SCIP_RETCODE	computeRanks (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *absranks, SCIP_Real *ranks, SCIP_VAR **sortedvars)
static SCIP_Real	maximalslack (SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	storeSolution (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *transsol, SCIP_SOL *bestsol)
SCIP_RETCODE	SCIPapplyHeurDualval (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint)
static	SCIP_DECL_HEURFREE (heurFreeDualval)
static	SCIP_DECL_HEURINIT (heurInitDualval)
static	SCIP_DECL_HEUREXIT (heurExitDualval)
static	SCIP_DECL_HEURINITSOL (heurInitsolDualval)
static	SCIP_DECL_HEUREXITSOL (heurExitsolDualval)
static	SCIP_DECL_HEUREXEC (heurExecDualval)
SCIP_RETCODE	SCIPincludeHeurDualval (SCIP *scip)

Macro Definition Documentation

#define HEUR_NAME   "dualval"

Definition at line 43 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_DESC   "primal heuristic using dual values"

Definition at line 44 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_DISPCHAR   'Y'

Definition at line 45 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_PRIORITY   0

Definition at line 46 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_FREQ   -1

Definition at line 47 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_FREQOFS   0

Definition at line 48 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_MAXDEPTH   -1

Definition at line 49 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 50 of file heur_dualval.c.

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and SCIPincludeHeurDualval().

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 51 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define EVENTHDLR_NAME   "lpsol_dualval"

Definition at line 53 of file heur_dualval.c.

Referenced by SCIPincludeEventHdlrLPsol().

#define EVENTHDLR_DESC   "event handler for lp solution found"

Definition at line 54 of file heur_dualval.c.

Referenced by SCIPincludeEventHdlrLPsol().

#define DEFAULT_FORCEIMPROVEMENTS   FALSE

exit if objective doesn't improve

Definition at line 58 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_ONLYCHEAPER   TRUE

add constraint to ensure that discrete vars are improving

Definition at line 59 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_ONLYLEAVES   FALSE

disable the heuristic if it was not called at a leaf of the B&B tree

Definition at line 60 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_RELAXINDICATORS   FALSE

relax the indicator variables by introducing continuous copies

Definition at line 61 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_RELAXCONTVARS   FALSE

enable relaxation of continous variables

Definition at line 62 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_HEURVERBLEVEL   0

verblevel of the heuristic, default is 0 to display nothing

Definition at line 65 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_NLPVERBLEVEL   0

verblevel of the nlp solver, can be 0 or 1

Definition at line 66 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_RANKVALUE   10

number of ranks that should be displayed when the heuristic is called

Definition at line 67 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_MAXCALLS   25

maximal number of recursive calls of the heuristic (if dynamicdepth is off)

Definition at line 68 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_DYNAMICDEPTH   0

says if and how the recursion depth is computed at runtime

Definition at line 69 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_MAXEQUALRANKS   50

maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1

Definition at line 70 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_MINGAP   5.0

minimal gap for which we still run the heuristic, if gap is less we return without doing anything

Definition at line 73 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_LAMBDASLACK   1.0

value added to objective of slack variables, must not be zero

Definition at line 74 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define DEFAULT_LAMBDAOBJ   0.0

scaling factor for the objective function

Definition at line 75 of file heur_dualval.c.

Referenced by SCIPincludeHeurDualval().

#define BIG_VALUE   1E+10

Definition at line 1516 of file heur_dualval.c.

Referenced by fixDiscreteVars().

Function Documentation

static SCIP_DECL_EVENTINIT ( eventInitLPsol  )

static

initialization method of event handler (called after problem was transformed)

Definition at line 134 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_FIRSTLPSOLVED, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, and SCIPcatchEvent().

static SCIP_DECL_EVENTEXIT ( eventExitLPsol  )

static

deinitialization method of event handler (called before transformed problem is freed)

Definition at line 147 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_FIRSTLPSOLVED, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, and SCIPdropEvent().

static SCIP_DECL_EVENTEXEC ( eventExecLPsol  )

static

execution method of event handler

Definition at line 160 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemoryArray, SCIPconsGetHdlr(), SCIPeventhdlrGetData(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPgetDualsolLinear(), SCIPgetNOrigConss(), SCIPgetOrigConss(), SCIPgetStage(), SCIPgetTransformedCons(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPhashmapRemoveAll(), and SCIPverbMessage().

static SCIP_RETCODE SCIPincludeEventHdlrLPsol ( SCIP *  scip, SCIP_HEURDATA *  heurdata  )

static

includes event handler for best solution found

Parameters

scip	SCIP data structure
heurdata	heuristic data

Definition at line 210 of file heur_dualval.c.

References EVENTHDLR_DESC, EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeEventhdlrBasic(), SCIPsetEventhdlrExit(), and SCIPsetEventhdlrInit().

Referenced by createSubSCIP().

static SCIP_RETCODE releaseHashmapEntries ( SCIP *  scip, SCIP_HASHMAP *  hashmap, SCIP_Bool  isvarmap  )

static

releases all variables or constraints from given hash map

Parameters

scip	SCIP data structure
hashmap	hashmap
isvarmap	are the entries variables or constraints?

Definition at line 236 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPhashmapGetList(), SCIPhashmapGetNLists(), SCIPhashmapListGetImage(), SCIPhashmapListGetNext(), SCIPreleaseCons(), and SCIPreleaseVar().

Referenced by createSubSCIP(), and SCIP_DECL_HEUREXIT().

static SCIP_RETCODE releaseHashmapNLPRows ( SCIP *  scip, SCIP_HASHMAP *  hashmap  )

static

releases all NLP rows from given hash map

Parameters

scip	SCIP data structure
hashmap	hashmap

Definition at line 277 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPhashmapGetList(), SCIPhashmapGetNLists(), SCIPhashmapListGetImage(), SCIPhashmapListGetNext(), and SCIPreleaseNlRow().

Referenced by SCIP_DECL_HEUREXIT().

static SCIP_RETCODE addLinearConstraints ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_Bool  addcombconss, SCIP_Bool  addcontconss, SCIP_HEURDATA *  heurdata  )

static

adds linear constraints from a SCIP instance to its NLP

Parameters

scip	SCIP data structure
conshdlr	constraint handler for linear constraints
addcombconss	whether to add combinatorial linear constraints to NLP
addcontconss	whether to add continuous linear constraints to NLP
heurdata	heuristic data structure

Definition at line 308 of file heur_dualval.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPaddNlRow(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPhashmapInsert(), SCIPisRelLE(), SCIPreleaseNlRow(), SCIPvarGetType(), and TRUE.

Referenced by addLinearConstraintsToNlp().

static SCIP_RETCODE addVarboundConstraints ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_Bool  addcombconss, SCIP_Bool  addcontconss, SCIP_HEURDATA *  heurdata  )

static

adds variable bound constraints from a SCIP instance to its NLP

Parameters

scip	SCIP data structure
conshdlr	constraint handler for linear constraints
addcombconss	whether to add combinatorial linear constraints to NLP
addcontconss	whether to add continuous linear constraints to NLP
heurdata	heuristic data structure

Definition at line 385 of file heur_dualval.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddNlRow(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPhashmapInsert(), and SCIPvarGetType().

Referenced by addLinearConstraintsToNlp().

static SCIP_RETCODE addLogicOrConstraints ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_HEURDATA *  heurdata  )

static

adds logic-or constraints to NLP

Parameters

scip	SCIP data structure
conshdlr	constraint handler for linear constraints
heurdata	heuristic data structure

Definition at line 443 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddNlRow(), SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPfreeBufferArrayNull, SCIPgetNVarsLogicor(), SCIPgetVarsLogicor(), SCIPhashmapInsert(), and SCIPreallocBufferArray.

Referenced by addLinearConstraintsToNlp().

static SCIP_RETCODE addSetppcConstraints ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_HEURDATA *  heurdata  )

static

adds setppc constraints to NLP

Parameters

scip	SCIP data structure
conshdlr	constraint handler for linear constraints
heurdata	heuristic data structure

Definition at line 510 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPaddNlRow(), SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPerrorMessage, SCIPfreeBufferArrayNull, SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashmapInsert(), SCIPinfinity(), and SCIPreallocBufferArray.

Referenced by addLinearConstraintsToNlp().

static SCIP_RETCODE addKnapsackConstraints ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_HEURDATA *  heurdata  )

static

adds knapsack constraints to NLP

Parameters

scip	SCIP data structure
conshdlr	constraint handler for linear constraints
heurdata	heuristic data structure

Definition at line 602 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddNlRow(), SCIPallocBufferArray, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsEnabled(), SCIPcreateNlRow(), SCIPfreeBufferArrayNull, SCIPgetCapacityKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), SCIPgetWeightsKnapsack(), SCIPhashmapInsert(), SCIPinfinity(), and SCIPreallocBufferArray.

Referenced by addLinearConstraintsToNlp().

static SCIP_RETCODE addLinearConstraintsToNlp ( SCIP *  scip, SCIP_Bool  addcombconss, SCIP_Bool  addcontconss, SCIP_HEURDATA *  heurdata  )

static

adds combinatorial and/or continuous variants of linear constraints from a SCIP instance to its NLP

Parameters

scip	SCIP data structure
addcombconss	whether to add combinatorial linear constraints to NLP
addcontconss	whether to add continuous linear constraints to NLP
heurdata	heuristic data structure

Definition at line 674 of file heur_dualval.c.

References addKnapsackConstraints(), addLinearConstraints(), addLogicOrConstraints(), addSetppcConstraints(), addVarboundConstraints(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfindConshdlr().

Referenced by SCIPapplyHeurDualval().

static SCIP_RETCODE createSolFromSubScipSol ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_SOL **  sol, SCIP_SOL *  subsol  )

static

creates a SCIP_SOL in our SCIP space out of the SCIP_SOL from a sub-SCIP

Parameters

scip	SCIP data structure
heur	heuristic data structure
sol	buffer to store solution value; if pointing to NULL, a new solution is created, otherwise values in the given one are overwritten
subsol	solution of sub-SCIP

Definition at line 728 of file heur_dualval.c.

References NULL, REALABS, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPcreateOrigSol(), SCIPdebugMessage, SCIPfreeSol(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPgetOrigVarsData(), SCIPgetProbvarSum(), SCIPgetSolVal(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetTransVar(), and SCIPvarIsBinary().

Referenced by storeSolution().

static SCIP_RETCODE createSubSCIP ( SCIP *  scip, SCIP_HEURDATA *  heurdata  )

static

creates copy of CIP from problem in SCIP

Parameters

scip	SCIP data structure
heurdata	heuristic data structure

Definition at line 819 of file heur_dualval.c.

References BMSclearMemoryArray, FALSE, MAX, NULL, REALABS, releaseHashmapEntries(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocMemoryArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcaptureCons(), SCIPcaptureVar(), SCIPchgVarLbGlobal(), SCIPchgVarObj(), SCIPchgVarType(), SCIPchgVarUbGlobal(), SCIPconsAddUpgradeLocks(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcopyConss(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcopyVars(), SCIPcreate(), SCIPcreateConsIndicatorLinCons(), SCIPcreateConsLinear(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMessage, SCIPdelCons(), SCIPfindConshdlr(), SCIPfloor(), SCIPgetBinaryVarIndicator(), SCIPgetLinearConsIndicator(), SCIPgetNConss(), SCIPgetNegatedVar(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetOrigConss(), SCIPgetOrigVars(), SCIPgetProbName(), SCIPgetSlackVarIndicator(), SCIPgetTransformedCons(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapGetList(), SCIPhashmapGetNLists(), SCIPhashmapInsert(), SCIPhashmapListGetImage(), SCIPhashmapListGetNext(), SCIPhashmapListGetOrigin(), SCIPhashmapRemove(), SCIPhashmapRemoveAll(), SCIPincludeEventHdlrLPsol(), SCIPinfinity(), SCIPisFeasEQ(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetIntParam(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetTransVar(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsIntegral(), SCIPvarIsNegated(), sqrt(), and TRUE.

Referenced by SCIP_DECL_HEURINIT(), and SCIPapplyHeurDualval().

static SCIP_RETCODE freeSubSCIP ( SCIP *  scip, SCIP_HEURDATA *  heurdata  )

static

free sub-SCIP data structure

Parameters

scip	SCIP data structure
heurdata	heuristic data structure

Definition at line 1446 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPfree().

Referenced by SCIP_DECL_HEUREXIT().

static SCIP_RETCODE createSolFromNLP ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_SOL **  sol  )

static

create a solution from the values of current nonlinear program

Parameters

scip	SCIP data structure
heur	heuristic data structure
sol	buffer to store solution value; if pointing to NULL a new solution is created, otherwise values in the given one are overwritten

Definition at line 1467 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPcreateSol(), SCIPgetNOrigVars(), SCIPgetOrigVarsData(), SCIPheurGetData(), SCIPsetSolVal(), SCIPvarGetNLPSol(), SCIPvarGetTransVar(), and SCIPvarIsActive().

Referenced by SCIPapplyHeurDualval().

static SCIP_RETCODE fixDiscreteVars ( SCIP *  scip, SCIP_HEURDATA *  heurdata, SCIP_SOL *  refpoint, SCIP_SOL **  transsol  )

static

method to fix the (relaxed) discrete variables

Parameters

scip	SCIP data structure
heurdata	heuristic data structure
refpoint	point to take fixation of discrete variables from; if NULL, then LP solution is used
transsol	pointer to new created solution with fixed values as solution value

Definition at line 1520 of file heur_dualval.c.

References BIG_VALUE, MAX, MIN, NULL, REALABS, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPcreateOrigSol(), SCIPfloor(), SCIPgetLPSolstat(), SCIPgetSolVal(), SCIPhashmapGetImage(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetTransVar(), and SCIPvarGetUbGlobal().

Referenced by SCIPapplyHeurDualval().

static SCIP_RETCODE freeMemory ( SCIP *  scip, SCIP_HEURDATA *  heurdata, SCIP_SOL *  transsol, SCIP_Real *  absranks, SCIP_Real *  ranks, SCIP_VAR **  sortedvars, SCIP_Bool  beforeswitching, SCIP_Bool  clearswitchedvars  )

static

method to free memory before leaving the heuristic or jumping up in the recursion

Parameters

scip	scip data structure
heurdata	heuristic data structure
transsol	sol that has to be freed
absranks	array of absolute rank values
ranks	array of rank values
sortedvars	array of corresponding variables
beforeswitching	did we call this method before or after switching variables?
clearswitchedvars	says if we should clear switchedvars or not

Definition at line 1594 of file heur_dualval.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetOrigVarsData(), SCIPhashmapGetImage(), SCIPhashmapRemoveAll(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), and SCIPvarGetUbGlobal().

Referenced by SCIPapplyHeurDualval(), and storeSolution().

static SCIP_RETCODE computeRanks ( SCIP *  scip, SCIP_HEURDATA *  heurdata, SCIP_Real *  absranks, SCIP_Real *  ranks, SCIP_VAR **  sortedvars  )

static

computes the ranks, saves them into an array and sorts the variables according to absolute ranks

Parameters

scip	scip data structure
heurdata	heuristic data structure
absranks	array of absolute rank values
ranks	array of rank values
sortedvars	array of corresponding variables

Definition at line 1680 of file heur_dualval.c.

References NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetBinaryVarIndicator(), SCIPgetLinearConsIndicator(), SCIPgetTransformedCons(), SCIPhashmapGetImage(), SCIPisFeasEQ(), SCIPsortDownRealRealPtr(), SCIPvarGetLbGlobal(), SCIPvarGetNegatedVar(), SCIPvarGetTransVar(), SCIPvarGetUbGlobal(), and SCIPvarIsNegated().

Referenced by SCIPapplyHeurDualval().

static SCIP_Real maximalslack ( SCIP *  scip, SCIP_HEURDATA *  heurdata  )

static

compute maximal slack of a variable

Parameters

scip	scip data structure
heurdata	heuristic data structure

Definition at line 1811 of file heur_dualval.c.

References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPgetBestSol(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPgetSolVal(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPvarGetName(), SCIPvarGetNLPSol(), SCIPverbMessage(), and TRUE.

Referenced by SCIPapplyHeurDualval().

static SCIP_RETCODE storeSolution ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_RESULT *  result, SCIP_SOL *  transsol, SCIP_SOL *  bestsol  )

static

method called after a solution is found which is feasible in the original problem, stores it and cleans up

Parameters

scip	SCIP data structure
heur	heuristic data
result	pointer to store result of: did not run, solution found, no solution found, or fixing is infeasible (cutoff)
transsol	solution to fix variables
bestsol	solution we create a original scip solution from

Definition at line 1884 of file heur_dualval.c.

References createSolFromSubScipSol(), FALSE, freeMemory(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPcheckSolOrig(), SCIPdebugMessage, SCIPfreeSol(), SCIPgetNLPSolstat(), SCIPheurGetData(), SCIPheurSetFreq(), SCIPinfinity(), SCIPsolGetOrigObj(), SCIPtrySolFree(), SCIPverbMessage(), and TRUE.

Referenced by SCIPapplyHeurDualval().

SCIP_RETCODE SCIPapplyHeurDualval	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_RESULT *	result,
		SCIP_SOL *	refpoint
	)

main procedure of the dualval heuristic

Parameters

scip	original SCIP data structure
heur	heuristic data structure
result	pointer to store result of: did not run, solution found, no solution found, or fixing is infeasible (cutoff)
refpoint	point to take fixation of discrete variables from; if NULL, then LP solution is used

Definition at line 1975 of file heur_dualval.c.

References addLinearConstraintsToNlp(), computeRanks(), createSolFromNLP(), createSubSCIP(), FALSE, fixDiscreteVars(), freeMemory(), MAX, maximalslack(), MIN, NULL, REALABS, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_OPTIMAL, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPapplyHeurDualval(), SCIPchgRhsLinear(), SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPconsGetHdlr(), SCIPdebugMessage, SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetGap(), SCIPgetNLPBranchCands(), SCIPgetNLPSolstat(), SCIPgetNLPVars(), SCIPgetNNlpis(), SCIPgetNNLPVars(), SCIPgetNOrigConss(), SCIPgetNPseudoBranchCands(), SCIPgetOrigConss(), SCIPgetOrigVars(), SCIPgetOrigVarsData(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetStatus(), SCIPgetTransformedCons(), SCIPgetUpperbound(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPhashmapRemove(), SCIPhashmapRemoveAll(), SCIPheurGetData(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPisGE(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPisTransformed(), SCIPnlrowGetDualsol(), SCIPpresolve(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetNLPInitialGuess(), SCIPsetNLPIntPar(), SCIPsetSolVal(), SCIPsolve(), SCIPsolveNLP(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetOrigvarSum(), SCIPvarGetTransVar(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsNegated(), SCIPverbMessage(), storeSolution(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPapplyHeurDualval().

static SCIP_DECL_HEURFREE ( heurFreeDualval  )

static

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

Definition at line 2477 of file heur_dualval.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, and SCIPheurGetData().

static SCIP_DECL_HEURINIT ( heurInitDualval  )

static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 2494 of file heur_dualval.c.

References createSubSCIP(), HEUR_TIMING, NULL, SCIP_CALL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPblkmem(), SCIPhashmapCreate(), SCIPheurGetData(), SCIPheurGetFreq(), SCIPheurGetFreqofs(), SCIPheurSetTimingmask(), and SCIPsetIntParam().

static SCIP_DECL_HEUREXIT ( heurExitDualval  )

static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 2530 of file heur_dualval.c.

References FALSE, freeSubSCIP(), NULL, releaseHashmapEntries(), releaseHashmapNLPRows(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemoryArrayNull, SCIPfreeMemoryArray, SCIPgetNOrigConss(), SCIPgetOrigConss(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapRemoveAll(), SCIPheurGetData(), and TRUE.

static SCIP_DECL_HEURINITSOL ( heurInitsolDualval  )

static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 2670 of file heur_dualval.c.

References HEUR_TIMING, NULL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetFreq(), SCIPheurGetFreqofs(), and SCIPheurSetTimingmask().

static SCIP_DECL_HEUREXITSOL ( heurExitsolDualval  )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 2698 of file heur_dualval.c.

References HEUR_TIMING, NULL, SCIP_OKAY, and SCIPheurSetTimingmask().

static SCIP_DECL_HEUREXEC ( heurExecDualval  )

static

execution method of primal heuristic

Definition at line 2711 of file heur_dualval.c.

References FALSE, HEUR_TIMING, NULL, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPapplyHeurDualval(), SCIPheurGetData(), and SCIPheurSetTimingmask().

SCIP_RETCODE SCIPincludeHeurDualval

(

SCIP *

scip

)

creates the dualval primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2750 of file heur_dualval.c.

References BMSclearMemory, DEFAULT_DYNAMICDEPTH, DEFAULT_FORCEIMPROVEMENTS, DEFAULT_HEURVERBLEVEL, DEFAULT_LAMBDAOBJ, DEFAULT_LAMBDASLACK, DEFAULT_MAXCALLS, DEFAULT_MAXEQUALRANKS, DEFAULT_MINGAP, DEFAULT_NLPVERBLEVEL, DEFAULT_ONLYCHEAPER, DEFAULT_ONLYLEAVES, DEFAULT_RANKVALUE, DEFAULT_RELAXCONTVARS, DEFAULT_RELAXINDICATORS, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPinfinity(), SCIPsetHeurExit(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), SCIPsetHeurInitsol(), and TRUE.

Referenced by SCIPincludeDefaultPlugins().