SCIP Doxygen Documentation
Loading...
Searching...
No Matches

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   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.

◆ 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.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 55 of file heur_octane.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1008000

Definition at line 56 of file heur_octane.c.

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 57 of file heur_octane.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 58 of file heur_octane.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 59 of file heur_octane.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 60 of file heur_octane.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 61 of file heur_octane.c.

◆ 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()

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
scipSCIP data structure
facetsfacets got so far
lambdadistances of the facets
icurrent facet
jcomponent to flip
f_maxmaximal number of facets to create
nsubspacevarsdimension of the fractional space
lamdistance of the current facet
nfacetsnumber of facets

Definition at line 90 of file heur_octane.c.

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

Referenced by generateNeighborFacets().

◆ getSolFromFacet()

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
scipSCIP data structure
facetcurrent facet
solsolution to create
signmarker for retransformation
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space

Definition at line 135 of file heur_octane.c.

References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPlinkLPSol(), SCIPsetSolVal(), and sol.

Referenced by SCIP_DECL_HEUREXEC().

◆ generateObjectiveRay()

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
scipSCIP data structure
raydirectionshooting ray
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space

Definition at line 172 of file heur_octane.c.

References assert(), NULL, SCIP_OKAY, SCIP_Real, and SCIPvarGetObj().

Referenced by SCIP_DECL_HEUREXEC().

◆ generateDifferenceRay()

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
scipSCIP data structure
raydirectionshooting ray
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space

Definition at line 192 of file heur_octane.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ generateAverageRay()

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
scipSCIP data structure
raydirectionshooting ray
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space
weightedshould the rays be weighted?

Definition at line 214 of file heur_octane.c.

References assert(), BMSclearMemoryArray, FALSE, i, 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()

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
scipSCIP data structure
raydirectionshooting ray
fracspaceindex set of fractional variables
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space

Definition at line 419 of file heur_octane.c.

References assert(), i, 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 var.

Referenced by SCIP_DECL_HEUREXEC().

◆ generateStartingPoint()

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

generates the starting point for the shooting ray in original coordinates

Parameters
scipSCIP data structure
rayoriginorigin of the shooting ray
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space

Definition at line 517 of file heur_octane.c.

References assert(), NULL, SCIP_Real, and SCIPvarGetLPSol().

Referenced by SCIP_DECL_HEUREXEC().

◆ flipCoords()

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
rayoriginorigin of the shooting ray
raydirectiondirection of the shooting ray
signmarker for flipped coordinates
nsubspacevarsdimension of fractional space

Definition at line 538 of file heur_octane.c.

References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ generateNeighborFacets()

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
scipSCIP data structure
facetsfacets got so far
lambdadistances of the facets
rayoriginorigin of the shooting ray
raydirectiondirection of the shooting ray
negquotientarray by which coordinates are sorted
nsubspacevarsdimension of fractional space
f_maxmaximal number of facets to create
icurrent facet
nfacetsnumber of facets

Definition at line 569 of file heur_octane.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ isZero()

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

tests, whether an array is completely zero

Parameters
scipSCIP data structure
raydirectionarray to be checked
nsubspacevarssize of array

Definition at line 662 of file heur_octane.c.

References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisFeasZero(), SCIPisInfinity(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

SCIP_DECL_HEURCOPY ( heurCopyOctane )
static

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

Definition at line 693 of file heur_octane.c.

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

◆ SCIP_DECL_HEURFREE()

SCIP_DECL_HEURFREE ( heurFreeOctane )
static

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

Definition at line 707 of file heur_octane.c.

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

◆ SCIP_DECL_HEURINIT()

SCIP_DECL_HEURINIT ( heurInitOctane )
static

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

Definition at line 727 of file heur_octane.c.

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

◆ SCIP_DECL_HEUREXIT()

SCIP_DECL_HEUREXIT ( heurExitOctane )
static

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

Definition at line 752 of file heur_octane.c.

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

◆ SCIP_DECL_HEUREXEC()