53#define HEUR_NAME "octane"
54#define HEUR_DESC "octane primal heuristic for pure {0;1}-problems based on Balas et al."
55#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
56#define HEUR_PRIORITY -1008000
59#define HEUR_MAXDEPTH -1
60#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
61#define HEUR_USESSUBSCIP FALSE
63#define DEFAULT_FMAX 100
64#define DEFAULT_FFIRST 10
65#define DEFAULT_USEFRACSPACE TRUE
74 SCIP_Bool usefracspace;
78 SCIP_Bool useavgwgtray;
79 SCIP_Bool useavgnbray;
102 SCIP_Bool* lastfacet;
113 lastfacet = facets[f_max];
118 lambda[k] = lambda[k-1];
119 facets[k] = facets[k-1];
124 facets[k] = lastfacet;
129 facets[k][j] = !facets[k][j];
153 for( v = nsubspacevars - 1; v >= 0; --v )
157 if( facet[v] == sign[v] )
174 SCIP_Real* raydirection,
185 for( v = nsubspacevars - 1; v >= 0; --v )
194 SCIP_Real* raydirection,
205 for( v = nsubspacevars - 1; v >= 0; --v )
216 SCIP_Real* raydirection,
223 SCIP_Real** tableaurows;
226 int** tableaurowinds;
227 int* ntableaurowinds;
228 SCIP_Bool* usedrowids =
NULL;
240 assert(nsubspacevars > 0);
251 for( j = nsubspacevars - 1; j >= 0; --j )
265 for( j = nsubspacevars - 1; j >= 0; --j )
270 if( ntableaurowinds[j] == -1 )
272 assert(sparse == 0 || sparse == -1);
275 for(
i = nrows - 1;
i >= 0; --
i )
276 rownorm[
i] += tableaurows[j][
i] * tableaurows[j][
i];
280 assert(sparse == 1 || sparse == -1);
284 if( usedrowids ==
NULL )
291 for(
i = ntableaurowinds[j] - 1;
i >= 0; --
i )
293 tableaurowind = tableaurowinds[j][
i];
294 rownorm[tableaurowind] += tableaurows[j][tableaurowind] * tableaurows[j][tableaurowind];
296 if( !usedrowids[tableaurowind] )
298 usedrowids[tableaurowind] =
TRUE;
299 rowids[nrowids] = tableaurowind;
311 for(
i = nrows - 1;
i >= 0; --
i )
316 rownorm[
i] = sqrt(rownorm[
i]);
327 for( j = nsubspacevars - 1; j >= 0; --j )
329 raydirection[j] += tableaurows[j][
i] / (rownorm[
i] * rowweight);
337 SCIP_Real* rowweights;
344 assert(0 <= nrowids && nrowids <= nrows);
349 for(
i = nrowids - 1;
i >= 0; --
i )
362 rownorm[
r] = sqrt(rownorm[
r]);
381 for( j = nsubspacevars - 1; j >= 0; --j )
383 for( k = ntableaurowinds[j] - 1; k >= 0; --k )
385 tableaurowind = tableaurowinds[j][k];
387 if( usedrowids[tableaurowind] )
389 raydirection[j] += tableaurows[j][tableaurowind] / (rownorm[tableaurowind] * rowweights[tableaurowind]);
404 for( j = 0; j < nsubspacevars; ++j )
421 SCIP_Real* raydirection,
442 for(
i = nsubspacevars - 1;
i >= 0; --
i )
449 raydirection[
i] = +1.0;
451 raydirection[
i] = -1.0;
453 raydirection[
i] = 0.0;
457 for(
i = nrows - 1;
i >= 0; --
i )
481 for( j = nnonz - 1; j >= 0; --j )
486 rownorm += coeffs[j] * coeffs[j];
494 rownorm = sqrt(rownorm);
497 for( j = nnonz - 1; j >= 0; --j )
507 raydirection[f] += factor * coeffs[j] / rownorm;
519 SCIP_Real* rayorigin,
530 for( v = nsubspacevars - 1; v >= 0; --v )
539 SCIP_Real* rayorigin,
540 SCIP_Real* raydirection,
551 for( v = nsubspacevars - 1; v >= 0; --v )
554 if( raydirection[v] < 0 )
557 raydirection[v] *= -1.0;
558 rayorigin[v] *= -1.0;
573 SCIP_Real* rayorigin,
574 SCIP_Real* raydirection,
575 SCIP_Real* negquotient,
599 p = 0.5 * nsubspacevars;
601 for( j = nsubspacevars - 1; j >= 0; --j )
606 q += raydirection[j];
611 q -= raydirection[j];
617 for( j = 0; j < nsubspacevars; ++j )
634 for( j = 0; j < nsubspacevars && !facets[
i][j] &&
SCIPisFeasGT(
scip, negquotient[j], lambda[
i]); ++j )
638 lam = (p - 2*rayorigin[j]) / (q + 2*raydirection[j]);
639 tryToInsert(
scip, facets, lambda,
i, j, f_max, nsubspacevars, lam, nfacets);
645 for( j = nsubspacevars - 1; j >= 0 && facets[
i][j] &&
SCIPisFeasLE(
scip, negquotient[j], lambda[
i]); --j )
649 lam = (p + 2*rayorigin[j]) / (q - 2*raydirection[j]);
650 if( negquotient[minplus] <= lam )
651 tryToInsert(
scip, facets, lambda,
i, j, f_max, nsubspacevars, lam, nfacets);
655 for( j = 1; j < f_max; j++)
664 SCIP_Real* raydirection,
674 for( v = nsubspacevars - 1; v >= 0; --v )
681 raydirection[v] = 0.0;
786 SCIP_Real* rayorigin;
787 SCIP_Real* raydirection;
788 SCIP_Real* negquotient;
791 SCIP_Bool usefracspace;
860 usefracspace =
heurdata->usefracspace;
867 nsubspacevars = nfracvars;
872 for(
i = nsubspacevars - 1;
i >= 0; --
i )
879 nsubspacevars =
nvars;
888 subspacevars[currentindex] =
vars[
i];
889 fracspace[
i] = currentindex;
901 if( nsubspacevars == 0 )
908 assert(0 < nsubspacevars && nsubspacevars <=
nvars);
910 for(
i = 0;
i < nsubspacevars;
i++)
914 if( nsubspacevars < 30 )
918 f_max =
MIN(f_max, 1 << (nsubspacevars - 1) );
921 f_first =
MIN(f_first, f_max);
932 for(
i = f_max;
i >= 0; --
i )
942 SCIPdebugMsg(
scip,
"run Octane heuristic on %s variables, which are %d vars, generate at most %d facets, using rule number %d\n",
943 usefracspace ?
"fractional" :
"all", nsubspacevars, f_max, (
heurdata->lastrule+1)%5);
947 for(
i = nsubspacevars - 1;
i >= 0; --
i )
996 if(
isZero(
scip, raydirection, nsubspacevars) )
1000 flipCoords(rayorigin, raydirection, sign, nsubspacevars);
1002 for(
i = f_max - 1;
i >= 0; --
i)
1006 p = 0.5 * nsubspacevars;
1008 for(
i = nsubspacevars - 1;
i >= 0; --
i )
1013 if( rayorigin[
i] < 0 )
1019 negquotient[
i] = - (rayorigin[
i] / raydirection[
i]);
1024 facets[0][
i] =
TRUE;
1026 q += raydirection[
i];
1035 for(
i = 0;
i < nsubspacevars;
i++ )
1037 assert( raydirection[
i] >= 0 );
1040 for(
i = 1;
i < nsubspacevars;
i++ )
1041 assert( negquotient[
i - 1] >= negquotient[
i] );
1049 p += 2 * rayorigin[
i];
1050 q -= 2 * raydirection[
i];
1066 for(
i = 0;
i < nfacets &&
i < f_first; ++
i)
1070 for(
i = 0;
i < nfacets &&
i < f_first; ++
i )
1080 for(
i = nrows - 1;
i >= 0; --
i )
1102 for( j = nnonzerovars - 1; j >= 0; --j )
1109 for( k =
MIN(f_first, nfacets) - 1; k > 0; --k )
1112 for( j = nnonzerovars - 1; j >= 0; --j )
1122 else if( rhs < rowval )
1125 for( k =
MIN(f_first, nfacets) - 1; k > 0; --k )
1128 for( j = nnonzerovars - 1; j >= 0; --j )
1146 for(
i =
MIN(f_first, nfacets) - 1;
i >= 0; --
i )
1154 for(
i = f_first;
i < f_max; ++
i)
1167 for(
i =
MIN(f_first, nfacets) - 1;
i >= 0; --
i )
1179 for(
i = 0;
i <= f_max; ++
i )
1225 "heuristics/octane/fmax",
1226 "number of 0-1-points to be tested as possible solutions by OCTANE",
1230 "heuristics/octane/ffirst",
1231 "number of 0-1-points to be tested at first whether they violate a common row",
1235 "heuristics/octane/usefracspace",
1236 "execute OCTANE only in the space of fractional variables (TRUE) or in the full space?",
1240 "heuristics/octane/useobjray",
1241 "should the inner normal of the objective be used as one ray direction?",
1245 "heuristics/octane/useavgray",
1246 "should the average of the basic cone be used as one ray direction?",
1250 "heuristics/octane/usediffray",
1251 "should the difference between the root solution and the current LP solution be used as one ray direction?",
1255 "heuristics/octane/useavgwgtray",
1256 "should the weighted average of the basic cone be used as one ray direction?",
1260 "heuristics/octane/useavgnbray",
1261 "should the weighted average of the nonbasic cone be used as one ray direction?",
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
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)
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)
SCIP_RETCODE SCIPincludeHeurOctane(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
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)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvACol(SCIP *scip, int c, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
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)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
void SCIPsortDownRealRealRealBoolPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Real *realarray3, SCIP_Bool *boolarray, void **ptrarray, int len)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
static SCIP_RETCODE generateDifferenceRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars)
#define DEFAULT_USEFRACSPACE
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 void flipCoords(SCIP_Real *rayorigin, SCIP_Real *raydirection, SCIP_Bool *sign, int nsubspacevars)
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_Bool isZero(SCIP *scip, SCIP_Real *raydirection, int nsubspacevars)
static SCIP_RETCODE generateAverageRay(SCIP *scip, SCIP_Real *raydirection, SCIP_VAR **subspacevars, int nsubspacevars, SCIP_Bool weighted)
static void generateStartingPoint(SCIP *scip, SCIP_Real *rayorigin, SCIP_VAR **subspacevars, int nsubspacevars)
static SCIP_RETCODE generateAverageNBRay(SCIP *scip, SCIP_Real *raydirection, int *fracspace, SCIP_VAR **subspacevars, 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)
octane primal heuristic based on Balas, Ceria, Dawande, Margot, and Pataki
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
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
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
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Retcode SCIP_RETCODE