octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
Definition in file heur_octane.c.
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) |
#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().
|
static |
tries to insert the facet obtained from facet i flipped in component j into the list of the fmax nearest facets
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().
|
static |
constructs a solution from a given facet paying attention to the transformations made at the beginning of OCTANE
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().
|
static |
generates the direction of the shooting ray as the inner normal of the objective function
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().
|
static |
generates the direction of the shooting ray as the difference between the root and the current LP solution
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().
|
static |
generates the direction of the shooting ray as the average of the extreme rays of the basic cone
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().
|
static |
generates the direction of the shooting ray as the average of the normalized non-basic vars and rows
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().
|
static |
generates the starting point for the shooting ray in original coordinates
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().
|
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
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.
Referenced by SCIP_DECL_HEUREXEC().
|
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
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().
tests, whether an array is completely zero
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().
|
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().
|
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().
|
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().
|
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().
|
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.