heur_octane.c
Go to the documentation of this file.
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
65#define DEFAULT_USEFRACSPACE TRUE /**< use heuristic for the space of fractional variables or for whole space? */
72 int f_first; /**< {0,1}-points to be generated at first in order to check whether restart is necessary */
74 SCIP_Bool usefracspace; /**< use heuristic for the space of fractional variables or for the whole space? */
75 SCIP_Bool useobjray; /**< should the inner normal of the objective be used as one ray direction? */
76 SCIP_Bool useavgray; /**< should the average ray of the basic cone be used as one ray direction? */
77 SCIP_Bool usediffray; /**< should difference between root sol and current LP sol be used as one ray direction? */
78 SCIP_Bool useavgwgtray; /**< should the weighted average ray of the basic cone be used as one ray direction? */
79 SCIP_Bool useavgnbray; /**< should the average ray of the nonbasic cone be used as one ray direction? */
88/** tries to insert the facet obtained from facet i flipped in component j into the list of the fmax nearest facets */
123 /* inserting new facet into list, new facet is facet at position i flipped in coordinate j, new distance lam */
133/** constructs a solution from a given facet paying attention to the transformations made at the beginning of OCTANE */
155 /* after permutation, a variable should be set to 1, iff there was no reflection in this coordinate and the hit
190/** generates the direction of the shooting ray as the difference between the root and the current LP solution */
212/** generates the direction of the shooting ray as the average of the extreme rays of the basic cone */
268 SCIP_CALL( SCIPgetLPBInvACol(scip, SCIPcolGetLPPos(SCIPvarGetCol(subspacevars[j])), tableaurows[j], tableaurowinds[j], &ntableaurowinds[j]) );
389 raydirection[j] += tableaurows[j][tableaurowind] / (rownorm[tableaurowind] * rowweights[tableaurowind]);
417/** generates the direction of the shooting ray as the average of the normalized non-basic vars and rows */
534/** translates the inner point of the LP to an inner point rayorigin of the unit hyper octahedron and
632 /* reverse search for facets from which the actual facet can be got by a single, decreasing + to - flip */
633 /* a facet will be inserted into the queue, iff it is one of the fmax closest ones already found */
634 for( j = 0; j < nsubspacevars && !facets[i][j] && SCIPisFeasGT(scip, negquotient[j], lambda[i]); ++j )
643 /* reverse search for facets from which the actual facet can be got by a single, nonincreasing - to + flip */
644 /* a facet will be inserted into the queue, iff it is one of the fmax closest ones already found */
645 for( j = nsubspacevars - 1; j >= 0 && facets[i][j] && SCIPisFeasLE(scip, negquotient[j], lambda[i]); --j )
776 SCIP_SOL** first_sols; /* stores the first ffirst sols in order to check for common violation of a row */
780 SCIP_VAR** subspacevars; /* the variables on which the search is performed. Either coinciding with vars or with the
791 SCIP_Bool usefracspace; /* determines whether the search concentrates on fractional variables and fixes integer ones */
792 SCIP_Bool cons_viol; /* used for checking whether a linear constraint is violated by one of the possible solutions */
805 int f_first; /* {0,1}-points to be generated at first in order to check whether a restart is necessary */
846 if( SCIPgetNNodes(scip) % (SCIPheurGetNCalls(heur) / (100 * SCIPheurGetNBestSolsFound(heur) + 10*heurdata->nsuccess + 1) + 1) != 0 )
864 /* determine the space one which OCTANE should work either as the whole space or as the space of fractional variables */
942 SCIPdebugMsg(scip, "run Octane heuristic on %s variables, which are %d vars, generate at most %d facets, using rule number %d\n",
1010 /* calculate negquotient, the ratio of rayorigin and raydirection, paying special attention to the case raydirection[i] == 0 */
1032 SCIPsortDownRealRealRealBoolPtr(negquotient, raydirection, rayorigin, sign, (void**) subspacevars, nsubspacevars);
1045 /* find the first facet of the octahedron hit by a ray shot from rayorigin into direction raydirection */
1067 generateNeighborFacets(scip, facets, lambda, rayorigin, raydirection, negquotient, nsubspacevars, f_max, i, &nfacets);
1073 SCIP_CALL( getSolFromFacet(scip, facets[i], first_sols[i], sign, subspacevars, nsubspacevars) );
1105 /* if the row's lhs is violated by the first sol, test, whether it is violated by the next ones, too */
1145 /* if there was no row violated by all solutions, try whether one or more of them are feasible */
1153 /* search for further facets and construct and try solutions out of facets fixed as closest ones */
1158 generateNeighborFacets(scip, facets, lambda, rayorigin, raydirection, negquotient, nsubspacevars, f_max, i, &nfacets);
1251 "should the difference between the root solution and the current LP solution be used as one ray direction?",
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_RETCODE SCIPgetLPBInvACol(SCIP *scip, int c, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:819
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:471
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:2954
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
void SCIPsortDownRealRealRealBoolPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Real *realarray3, SCIP_Bool *boolarray, void **ptrarray, int len)
static SCIP_RETCODE generateDifferenceRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:192
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)
Definition: heur_octane.c:90
static void flipCoords(SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Bool *sign, int nsubspacevars)
Definition: heur_octane.c:538
static SCIP_RETCODE getSolFromFacet(SCIP *scip, SCIP_Bool *facet, SCIP_SOL *sol, SCIP_Bool *sign, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:135
static SCIP_RETCODE generateObjectiveRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:172
static SCIP_Bool isZero(SCIP *scip, SCIP_Real *raydirection, int nsubspacevars)
Definition: heur_octane.c:662
static SCIP_RETCODE generateAverageRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars, SCIP_Bool weighted)
Definition: heur_octane.c:214
static void generateStartingPoint(SCIP *scip, SCIP_Real *rayorigin, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:517
static SCIP_RETCODE generateAverageNBRay(SCIP *scip, SCIP_Real *raydirection, int *fracspace, SCIP_VAR **subspacevars, int nsubspacevars)
Definition: heur_octane.c:419
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)
Definition: heur_octane.c:569
octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
memory allocation routines
Definition: objbenders.h:44
public methods for primal heuristics
public methods for LP management
public methods for message output
methods for sorting joint arrays of various types
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
Definition: struct_lp.h:136
Definition: struct_heur.h:98
Definition: struct_lp.h:202
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70