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"

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

◆ HEUR_NAME

#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().

◆ HEUR_DESC

#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().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'O'

Definition at line 30 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1008000

Definition at line 31 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 32 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 33 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 34 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE

Definition at line 35 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 36 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ DEFAULT_FMAX

#define DEFAULT_FMAX 100

{0,1}-points to be checked

Definition at line 38 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ DEFAULT_FFIRST

#define DEFAULT_FFIRST 10

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

Definition at line 39 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ DEFAULT_USEFRACSPACE

#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

◆ tryToInsert()

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, SCIP_Bool, SCIPisFeasGE(), SCIPisFeasGT(), and SCIPisFeasLE().

Referenced by generateNeighborFacets().

◆ getSolFromFacet()

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 SCIP_CALL, SCIP_OKAY, SCIPlinkLPSol(), and SCIPsetSolVal().

Referenced by SCIP_DECL_HEUREXEC().

◆ generateObjectiveRay()

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 SCIP_OKAY, and SCIPvarGetObj().

Referenced by SCIP_DECL_HEUREXEC().

◆ generateDifferenceRay()

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 SCIP_OKAY, SCIPvarGetLPSol(), and SCIPvarGetRootSol().

Referenced by SCIP_DECL_HEUREXEC().

◆ generateAverageRay()

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 BMSclearMemoryArray, FALSE, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPfreeBufferArray, SCIPgetLPBInvACol(), SCIPgetLPRowsData(), SCIPisFeasZero(), SCIPisInfinity(), SCIProwGetDualsol(), SCIPvarGetCol(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ generateAverageNBRay()

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 393 of file heur_octane.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ generateStartingPoint()

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 491 of file heur_octane.c.

References SCIP_OKAY, and SCIPvarGetLPSol().

Referenced by SCIP_DECL_HEUREXEC().

◆ flipCoords()

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 514 of file heur_octane.c.

References FALSE, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ generateNeighborFacets()

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 545 of file heur_octane.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ isZero()

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 638 of file heur_octane.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyOctane )

static

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

Definition at line 669 of file heur_octane.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeOctane )

static

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

Definition at line 683 of file heur_octane.c.

References HEUR_NAME, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitOctane )

static

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

Definition at line 703 of file heur_octane.c.

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

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitOctane )

static

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

Definition at line 728 of file heur_octane.c.

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecOctane )

static

execution method of primal heuristic

Definition at line 748 of file heur_octane.c.

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

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_FMAX

◆ DEFAULT_FFIRST

◆ DEFAULT_USEFRACSPACE

Function Documentation

◆ tryToInsert()

◆ getSolFromFacet()

◆ generateObjectiveRay()

◆ generateDifferenceRay()

◆ generateAverageRay()

◆ generateAverageNBRay()

◆ generateStartingPoint()

◆ flipCoords()

◆ generateNeighborFacets()

◆ isZero()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEUREXEC()