heur_octane.c File Reference

Detailed Description

octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki

Author

Timo Berthold

Definition in file heur_octane.c.

#include <assert.h>
#include <string.h>
#include <math.h>
#include "scip/heur_octane.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME   "octane"
#define	HEUR_DESC   "octane primal heuristic for pure {0;1}-problems based on Balas et al."
#define	HEUR_DISPCHAR   'O'
#define	HEUR_PRIORITY   -1008000
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE
#define	HEUR_USESSUBSCIP   FALSE
#define	DEFAULT_FMAX   100
#define	DEFAULT_FFIRST   10
#define	DEFAULT_USEFRACSPACE   TRUE

Functions
static void	tryToInsert (SCIP *scip, SCIP_Bool **facets, SCIP_Real *lambda, int i, int j, int f_max, int nsubspacevars, SCIP_Real lam, int *nfacets)
static SCIP_RETCODE	getSolFromFacet (SCIP *scip, SCIP_Bool *facet, SCIP_SOL *sol, SCIP_Bool *sign, SCIP_VAR **subspacevars, int nsubspacevars)
static SCIP_RETCODE	generateObjectiveRay (SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
static SCIP_RETCODE	generateDifferenceRay (SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
static SCIP_RETCODE	generateAverageRay (SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars, SCIP_Bool weighted)
static SCIP_RETCODE	generateAverageNBRay (SCIP *scip, SCIP_Real *raydirection, int *fracspace, SCIP_VAR **subspacevars, int nsubspacevars)
static SCIP_RETCODE	generateStartingPoint (SCIP *scip, SCIP_Real *rayorigin, SCIP_VAR **subspacevars, int nsubspacevars)
static void	flipCoords (SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Bool *sign, int nsubspacevars)
static void	generateNeighborFacets (SCIP *scip, SCIP_Bool **facets, SCIP_Real *lambda, SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Real *negquotient, int nsubspacevars, int f_max, int i, int *nfacets)
static SCIP_Bool	isZero (SCIP *scip, SCIP_Real *raydirection, int nsubspacevars)
static	SCIP_DECL_HEURCOPY (heurCopyOctane)
static	SCIP_DECL_HEURFREE (heurFreeOctane)
static	SCIP_DECL_HEURINIT (heurInitOctane)
static	SCIP_DECL_HEUREXIT (heurExitOctane)
static	SCIP_DECL_HEUREXEC (heurExecOctane)
SCIP_RETCODE	SCIPincludeHeurOctane (SCIP *scip)

Macro Definition Documentation

#define HEUR_NAME   "octane"

Definition at line 28 of file heur_octane.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINIT(), and SCIPincludeHeurOctane().

#define HEUR_DESC   "octane primal heuristic for pure {0;1}-problems based on Balas et al."

Definition at line 29 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_DISPCHAR   'O'

Definition at line 30 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_PRIORITY   -1008000

Definition at line 31 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_FREQ   -1

Definition at line 32 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_FREQOFS   0

Definition at line 33 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_MAXDEPTH   -1

Definition at line 34 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 35 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 36 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define DEFAULT_FMAX   100

{0,1}-points to be checked

Definition at line 38 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define DEFAULT_FFIRST   10

{0,1}-points to be generated at first

Definition at line 39 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

#define DEFAULT_USEFRACSPACE   TRUE

use heuristic for the space of fractional variables or for whole space?

Definition at line 40 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

Function Documentation

static void tryToInsert ( SCIP *  scip, SCIP_Bool **  facets, SCIP_Real *  lambda, int  i, int  j, int  f_max, int  nsubspacevars, SCIP_Real  lam, int *  nfacets  )

static

tries to insert the facet obtained from facet i flipped in component j into the list of the fmax nearest facets

Parameters

scip	SCIP data structure
facets	facets got so far
lambda	distances of the facets
i	current facet
j	component to flip
f_max	maximal number of facets to create
nsubspacevars	dimension of the fractional space
lam	distance of the current facet
nfacets	number of facets

Definition at line 65 of file heur_octane.c.

References BMScopyMemoryArray, NULL, SCIP_Bool, SCIPisFeasGE(), SCIPisFeasGT(), and SCIPisFeasLE().

Referenced by generateNeighborFacets().

static SCIP_RETCODE getSolFromFacet ( SCIP *  scip, SCIP_Bool *  facet, SCIP_SOL *  sol, SCIP_Bool *  sign, SCIP_VAR **  subspacevars, int  nsubspacevars  )

static

constructs a solution from a given facet paying attention to the transformations made at the beginning of OCTANE

Parameters

scip	SCIP data structure
facet	current facet
sol	solution to create
sign	marker for retransformation
subspacevars	pointer to fractional space variables
nsubspacevars	dimension of fractional space

Definition at line 110 of file heur_octane.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPlinkLPSol(), and SCIPsetSolVal().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE generateObjectiveRay ( SCIP *  scip, SCIP_Real *  raydirection, SCIP_VAR **  subspacevars, int  nsubspacevars  )

static

generates the direction of the shooting ray as the inner normal of the objective function

Parameters

scip	SCIP data structure
raydirection	shooting ray
subspacevars	pointer to fractional space variables
nsubspacevars	dimension of fractional space

Definition at line 147 of file heur_octane.c.

References NULL, SCIP_OKAY, and SCIPvarGetObj().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE generateDifferenceRay ( SCIP *  scip, SCIP_Real *  raydirection, SCIP_VAR **  subspacevars, int  nsubspacevars  )

static

generates the direction of the shooting ray as the difference between the root and the current LP solution

Parameters

scip	SCIP data structure
raydirection	shooting ray
subspacevars	pointer to fractional space variables
nsubspacevars	dimension of fractional space

Definition at line 167 of file heur_octane.c.

References NULL, SCIP_OKAY, SCIPvarGetLPSol(), and SCIPvarGetRootSol().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE generateAverageRay ( SCIP *  scip, SCIP_Real *  raydirection, SCIP_VAR **  subspacevars, int  nsubspacevars, SCIP_Bool  weighted  )

static

generates the direction of the shooting ray as the average of the extreme rays of the basic cone

Parameters

scip	SCIP data structure
raydirection	shooting ray
subspacevars	pointer to fractional space variables
nsubspacevars	dimension of fractional space
weighted	should the rays be weighted?

Definition at line 189 of file heur_octane.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPfreeBufferArray, SCIPgetLPBInvACol(), SCIPgetLPRowsData(), SCIPisFeasZero(), SCIProwGetDualsol(), and SCIPvarGetCol().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE generateAverageNBRay ( SCIP *  scip, SCIP_Real *  raydirection, int *  fracspace, SCIP_VAR **  subspacevars, int  nsubspacevars  )

static

generates the direction of the shooting ray as the average of the normalized non-basic vars and rows

Parameters

scip	SCIP data structure
raydirection	shooting ray
fracspace	index set of fractional variables
subspacevars	pointer to fractional space variables
nsubspacevars	dimension of fractional space

Definition at line 273 of file heur_octane.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPcolGetVar(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPisFeasEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIProwGetCols(), SCIProwGetDualsol(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetProbindex(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE generateStartingPoint ( SCIP *  scip, SCIP_Real *  rayorigin, SCIP_VAR **  subspacevars, int  nsubspacevars  )

static

generates the starting point for the shooting ray in original coordinates

Parameters

scip	SCIP data structure
rayorigin	origin of the shooting ray
subspacevars	pointer to fractional space variables
nsubspacevars	dimension of fractional space

Definition at line 371 of file heur_octane.c.

References NULL, SCIP_OKAY, and SCIPvarGetLPSol().

Referenced by SCIP_DECL_HEUREXEC().

static void flipCoords ( SCIP_Real *  rayorigin, SCIP_Real *  raydirection, SCIP_Bool *  sign, int  nsubspacevars  )

static

translates the inner point of the LP to an inner point rayorigin of the unit hyper octahedron and transforms raydirection and rayorigin by reflections stored in sign

Parameters

rayorigin	origin of the shooting ray
raydirection	direction of the shooting ray
sign	marker for flipped coordinates
nsubspacevars	dimension of fractional space

Definition at line 394 of file heur_octane.c.

References FALSE, NULL, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static void generateNeighborFacets ( SCIP *  scip, SCIP_Bool **  facets, SCIP_Real *  lambda, SCIP_Real *  rayorigin, SCIP_Real *  raydirection, SCIP_Real *  negquotient, int  nsubspacevars, int  f_max, int  i, int *  nfacets  )

static

generates all facets, from which facet i could be obtained by a decreasing + to - flip or a nonincreasing - to + flip and tests whether they are among the fmax nearest ones

Parameters

scip	SCIP data structure
facets	facets got so far
lambda	distances of the facets
rayorigin	origin of the shooting ray
raydirection	direction of the shooting ray
negquotient	array by which coordinates are sorted
nsubspacevars	dimension of fractional space
f_max	maximal number of facets to create
i	current facet
nfacets	number of facets

Definition at line 425 of file heur_octane.c.

References NULL, SCIP_Real, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasPositive(), and tryToInsert().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_Bool isZero ( SCIP *  scip, SCIP_Real *  raydirection, int  nsubspacevars  )

static

tests, whether an array is completely zero

Parameters

scip	SCIP data structure
raydirection	array to be checked
nsubspacevars	size of array

Definition at line 518 of file heur_octane.c.

References FALSE, NULL, SCIP_Bool, SCIPisFeasZero(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyOctane  )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 547 of file heur_octane.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurOctane().

static SCIP_DECL_HEURFREE ( heurFreeOctane  )

static

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

Definition at line 561 of file heur_octane.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

static SCIP_DECL_HEURINIT ( heurInitOctane  )

static

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

Definition at line 581 of file heur_octane.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPheurGetData(), and SCIPheurGetName().

static SCIP_DECL_HEUREXIT ( heurExitOctane  )

static

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

Definition at line 606 of file heur_octane.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().

static SCIP_DECL_HEUREXEC ( heurExecOctane  )

static

execution method of primal heuristic

Definition at line 626 of file heur_octane.c.

References BMSclearMemoryArray, BMScopyMemoryArray, FALSE, flipCoords(), generateAverageNBRay(), generateAverageRay(), generateDifferenceRay(), generateNeighborFacets(), generateObjectiveRay(), generateStartingPoint(), getSolFromFacet(), HEUR_NAME, isZero(), MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPcreateSol(), SCIPdebugMessage, SCIPerrorMessage, SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPinfinity(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisGE(), SCIPisLPSolBasic(), SCIPisPositive(), SCIPisStopped(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIPsortDownRealRealRealBoolPtr(), SCIPtrySol(), SCIPvarGetCol(), SCIPvarGetProbindex(), sign(), and TRUE.

SCIP_RETCODE SCIPincludeHeurOctane

(

SCIP *

scip

)

creates the octane primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1052 of file heur_octane.c.

References DEFAULT_FFIRST, DEFAULT_FMAX, DEFAULT_USEFRACSPACE, 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(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurFree(), SCIPsetHeurInit(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().