Detailed Description

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

Author: Timo Berthold

Definition in file heur_octane.c.

#include "blockmemshell/memory.h"
#include "scip/heur_octane.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include <string.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

◆ HEUR_NAME

#define HEUR_NAME "octane"

Definition at line 43 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 44 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'O'

Definition at line 45 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1008000

Definition at line 46 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 47 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 48 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 49 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE

Definition at line 50 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 51 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ DEFAULT_FMAX

#define DEFAULT_FMAX 100

{0,1}-points to be checked

Definition at line 53 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 54 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 55 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 80 of file heur_octane.c.

References BMScopyMemoryArray, NULL, 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 125 of file heur_octane.c.

References NULL, 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 162 of file heur_octane.c.

References NULL, 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 182 of file heur_octane.c.

References NULL, 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 204 of file heur_octane.c.

References BMSclearMemoryArray, FALSE, NULL, r, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPfreeBufferArray, SCIPgetLPBInvACol(), SCIPgetLPRowsData(), SCIPisFeasZero(), SCIPisInfinity(), SCIProwGetDualsol(), SCIPvarGetCol(), SQRT, 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 408 of file heur_octane.c.

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

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

References NULL, 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 529 of file heur_octane.c.

References FALSE, NULL, 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 560 of file heur_octane.c.

References NULL, 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 653 of file heur_octane.c.

References FALSE, NULL, 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 684 of file heur_octane.c.

References HEUR_NAME, NULL, 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 698 of file heur_octane.c.

References HEUR_NAME, NULL, 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 718 of file heur_octane.c.

References HEUR_NAME, NULL, 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 743 of file heur_octane.c.

References HEUR_NAME, NULL, 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 763 of file heur_octane.c.

References BMScopyMemoryArray, FALSE, flipCoords(), generateAverageNBRay(), generateAverageRay(), generateDifferenceRay(), generateNeighborFacets(), generateObjectiveRay(), generateStartingPoint(), getSolFromFacet(), HEUR_NAME, isZero(), MIN, NULL, r, 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()