Detailed Description
octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
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 SCIP_HEURDISPCHAR_ROUNDING |
#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 void | 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 53 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 54 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
Definition at line 55 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1008000 |
Definition at line 56 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 57 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 58 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 59 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 60 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 61 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
◆ DEFAULT_FMAX
#define DEFAULT_FMAX 100 |
{0,1}-points to be checked
Definition at line 63 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 64 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 65 of file heur_octane.c.
Referenced by SCIPincludeHeurOctane().
Function Documentation
◆ tryToInsert()
|
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 90 of file heur_octane.c.
References BMScopyMemoryArray, NULL, SCIP_Bool, SCIPisFeasGE(), SCIPisFeasGT(), and SCIPisFeasLE().
Referenced by generateNeighborFacets().
◆ getSolFromFacet()
|
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 135 of file heur_octane.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPlinkLPSol(), and SCIPsetSolVal().
Referenced by SCIP_DECL_HEUREXEC().
◆ generateObjectiveRay()
|
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 172 of file heur_octane.c.
References NULL, SCIP_OKAY, and SCIPvarGetObj().
Referenced by SCIP_DECL_HEUREXEC().
◆ generateDifferenceRay()
|
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 192 of file heur_octane.c.
References NULL, SCIP_OKAY, SCIPvarGetLPSol(), and SCIPvarGetRootSol().
Referenced by SCIP_DECL_HEUREXEC().
◆ generateAverageRay()
|
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 214 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(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ generateAverageNBRay()
|
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 419 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(), and SCIPvarGetUbLocal().
Referenced by SCIP_DECL_HEUREXEC().
◆ generateStartingPoint()
|
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 517 of file heur_octane.c.
References NULL, and SCIPvarGetLPSol().
Referenced by SCIP_DECL_HEUREXEC().
◆ flipCoords()
|
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 538 of file heur_octane.c.
References FALSE, NULL, and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ generateNeighborFacets()
|
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 569 of file heur_octane.c.
References NULL, SCIP_Real, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasPositive(), and tryToInsert().
Referenced by SCIP_DECL_HEUREXEC().
◆ isZero()
tests, whether an array is completely zero
- Parameters
-
scip SCIP data structure raydirection array to be checked nsubspacevars size of array
Definition at line 662 of file heur_octane.c.
References FALSE, NULL, SCIP_Bool, SCIPisFeasZero(), SCIPisInfinity(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 693 of file heur_octane.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurOctane().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 707 of file heur_octane.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 727 of file heur_octane.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPheurGetData(), and SCIPheurGetName().
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 752 of file heur_octane.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 772 of file heur_octane.c.
References BMScopyMemoryArray, FALSE, flipCoords(), generateAverageNBRay(), generateAverageRay(), generateDifferenceRay(), generateNeighborFacets(), generateObjectiveRay(), generateStartingPoint(), getSolFromFacet(), HEUR_NAME, isZero(), 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(), and TRUE.