Scippy

SCIP

Solving Constraint Integer Programs

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"

◆ HEUR_DESC

#define HEUR_DESC   "octane primal heuristic for pure {0;1}-problems based on Balas et al."

Definition at line 45 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 46 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1008000

Definition at line 47 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 48 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 49 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 50 of file heur_octane.c.

Referenced by SCIPincludeHeurOctane().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

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

Referenced by SCIPincludeHeurOctane().

◆ DEFAULT_FMAX

#define DEFAULT_FMAX   100

{0,1}-points to be checked

Definition at line 54 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 55 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 56 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
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 81 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
scipSCIP data structure
facetcurrent facet
solsolution to create
signmarker for retransformation
subspacevarspointer to fractional space variables
nsubspacevarsdimension of fractional space

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

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

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

Definition at line 205 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 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 410 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 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 508 of file heur_octane.c.

References NULL, 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
rayoriginorigin of the shooting ray
raydirectiondirection of the shooting ray
signmarker for flipped coordinates
nsubspacevarsdimension 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
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 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
scipSCIP data structure
raydirectionarray to be checked
nsubspacevarssize 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()