heuristics.c File Reference

Detailed Description

methods commonly used by primal heuristics

Author

Gregor Hendel

Definition in file heuristics.c.

#include "scip/heuristics.h"
#include "scip/cons_linear.h"
#include "scip/scip_exact.h"
#include "scip/scipdefplugins.h"
#include "scip/stat.h"
#include "scip/struct_scip.h"
#include "scip/pub_heur.h"
#include "scip/cons_indicator.h"
#include "scip/cons_sos1.h"

Go to the source code of this file.

Macros
#define	MINLPITER   10000

Functions
static SCIP_RETCODE	solveLP (SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
static SCIP_RETCODE	selectNextDiving (SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_Bool onlylpbranchcands, SCIP_Bool storelpcandscores, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Real *lpcandsscores, SCIP_Bool *lpcandroundup, int *nviollpcands, int nlpcands, SCIP_Bool *enfosuccess, SCIP_Bool *infeasible)
static SCIP_Longint	getDivesetIterLimit (SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_RETCODE	SCIPperformGenericDivingAlgorithm (SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
static SCIP_RETCODE	createRows (SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmap)
SCIP_RETCODE	SCIPcopyLargeNeighborhoodSearch (SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
SCIP_RETCODE	SCIPaddTrustregionNeighborhoodConstraint (SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)

Macro Definition Documentation

MINLPITER

#define MINLPITER   10000

minimal number of LP iterations allowed in each LP solving call

Definition at line 44 of file heuristics.c.

Function Documentation

solveLP()

SCIP_RETCODE solveLP ( SCIP * scip, SCIP_DIVESET * diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool * lperror, SCIP_Bool * cutoff )

static

solve probing LP

Parameters

scip	SCIP data structure
diveset	diving settings
maxnlpiterations	maximum number of allowed LP iterations
divecontext	context for diving statistics
lperror	pointer to store if an internal LP error occurred
cutoff	pointer to store whether the LP was infeasible

Definition at line 49 of file heuristics.c.

References assert(), cutoff, diveset, lperror, MAX, maxnlpiterations, MINLPITER, nlpiterations, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPdivesetGetName(), SCIPdivesetGetNLPIterations(), SCIPgetNLPIterations(), SCIPsolveProbingLP(), SCIPupdateDivesetLPStats(), and SCIPwarningMessage().

Referenced by SCIPperformGenericDivingAlgorithm().

selectNextDiving()

SCIP_RETCODE selectNextDiving ( SCIP * scip, SCIP_DIVESET * diveset, SCIP_SOL * worksol, SCIP_Bool onlylpbranchcands, SCIP_Bool storelpcandscores, SCIP_VAR ** lpcands, SCIP_Real * lpcandssol, SCIP_Real * lpcandsfrac, SCIP_Real * lpcandsscores, SCIP_Bool * lpcandroundup, int * nviollpcands, int nlpcands, SCIP_Bool * enfosuccess, SCIP_Bool * infeasible )

static

select the next variable and type of diving

Parameters

scip	SCIP data structure
diveset	dive set
worksol	current working solution
onlylpbranchcands	should only LP branching candidates be considered?
storelpcandscores	should the scores of the LP candidates be updated?
lpcands	LP branching candidates, or NULL if not needed
lpcandssol	solution values LP branching candidates, or NULL if not needed
lpcandsfrac	fractionalities of LP branching candidates, or NULL if not needed
lpcandsscores	array with LP branching candidate scores, or NULL
lpcandroundup	array to remember whether the preferred branching direction is upwards
nviollpcands	pointer to store the number of LP candidates whose solution value already violates local bounds
nlpcands	number of current LP cands
enfosuccess	pointer to store whether a candidate was sucessfully found
infeasible	pointer to store whether the diving can be immediately aborted because it is infeasible

Definition at line 93 of file heuristics.c.

References assert(), c, diveset, lpcands, lpcandsfrac, lpcandssol, nlpcands, NULL, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_DIVETYPE_INTEGRALITY, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPceil(), SCIPclearDiveBoundChanges(), SCIPfloor(), SCIPgetDiveBoundChanges(), SCIPgetDivesetScore(), SCIPgetSolVal(), SCIPisGE(), SCIPisLE(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIPperformGenericDivingAlgorithm().

getDivesetIterLimit()

SCIP_Longint getDivesetIterLimit ( SCIP * scip, SCIP_DIVESET * diveset, SCIP_DIVECONTEXT divecontext )

static

return the LP iteration budget suggestion for this dive set

Parameters

scip	SCIP data structure
diveset	dive set data structure
divecontext	context for diving statistics

Definition at line 178 of file heuristics.c.

References diveset, SCIP_Longint, SCIPdivesetGetMaxLPIterOffset(), SCIPdivesetGetMaxLPIterQuot(), SCIPdivesetGetNCalls(), SCIPdivesetGetNLPIterations(), SCIPdivesetGetSolSuccess(), and SCIPgetNNodeLPIterations().

Referenced by SCIPperformGenericDivingAlgorithm().

createRows()

SCIP_RETCODE createRows ( SCIP * scip, SCIP * subscip, SCIP_HASHMAP * varmap )

static

creates the rows of the subproblem

Parameters

scip	original SCIP data structure
subscip	SCIP data structure for the subproblem
varmap	a hashmap to store the mapping of source variables to the corresponding target variables

Definition at line 891 of file heuristics.c.

References assert(), FALSE, i, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcolGetVar(), SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPhashmapGetImage(), SCIPreleaseCons(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), and TRUE.

Referenced by SCIPcopyLargeNeighborhoodSearch().