62#define HEUR_NAME "farkasdiving"
63#define HEUR_DESC "LP diving heuristic that tries to construct a Farkas-proof"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
65#define HEUR_PRIORITY -900000
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
70#define HEUR_USESSUBSCIP FALSE
71#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE
72#define DIVESET_ISPUBLIC FALSE
79#define DEFAULT_MINRELDEPTH 0.0
80#define DEFAULT_MAXRELDEPTH 1.0
81#define DEFAULT_MAXLPITERQUOT 0.05
82#define DEFAULT_MAXLPITEROFS 1000
83#define DEFAULT_MAXDIVEUBQUOT 0.8
85#define DEFAULT_MAXDIVEAVGQUOT 0.0
87#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1
88#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0
89#define DEFAULT_BACKTRACK TRUE
90#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15
91#define DEFAULT_LPSOLVEFREQ 1
92#define DEFAULT_ONLYLPBRANCHCANDS FALSE
94#define DEFAULT_RANDSEED 151
96#define DEFAULT_MAXOBJOCC 1.0
97#define DEFAULT_OBJDYN 0.0001
98#define DEFAULT_CHECKCANDS FALSE
99#define DEFAULT_SCALESCORE TRUE
100#define DEFAULT_ROOTSUCCESS TRUE
102#define DEFAULT_SCALETYPE 'i'
109 SCIP_Real objdynamism;
111 SCIP_Bool glbchecked;
112 SCIP_Bool checkcands;
113 SCIP_Bool scalescore;
114 SCIP_Bool rootsuccess;
115 SCIP_Bool foundrootsol;
131 SCIP_Real lastobjcoef;
132 SCIP_Real objdynamism;
155 for(
i = 0;
i < ndivecands;
i++ )
167 if( nnzobjcoefs == 0 )
182 lastobjcoef = objcoefs[0];
187 objdynamism = log10(objcoefs[nnzobjcoefs-1] / objcoefs[0]);
189 SCIPdebugMsg(
scip,
"minabscoef: %g, maxabscoef: %g, objdym: %g\n", objcoefs[0], objcoefs[nnzobjcoefs-1], objdynamism);
192 if( objdynamism < heurdata->objdynamism )
209 for(
i = 1;
i < nnzobjcoefs;
i++ )
213 if( tmpmaxfreq > maxfreq )
214 maxfreq = tmpmaxfreq;
217 lastobjcoef = objcoefs[
i];
229 SCIPdebugMsg(
scip,
"%d divecands; %d nnzobjs; %d diffnnzobjs; %d maxfreq\n", ndivecands, nnzobjcoefs, ndiffnnzobjs,
233 if( maxfreq >
heurdata->maxobjocc * nnzobjcoefs )
271 SCIPdebugMsg(
scip,
" ---> disable farkasdiving (at least one global property is violated)\n");
446#define MIN_RAND 1e-06
447#define MAX_RAND 1e-05
496 *score *= (1.0 - candsfrac);
513 *score = -1.0 / *score;
521#define divesetAvailableFarkasdiving NULL
556 "should diving candidates be checked before running?",
560 "should the score be scaled?",
564 "should the heuristic only run within the tree if at least one solution was found at the root node?",
568 "maximal occurance factor of an objective coefficient",
572 "minimal objective dynamism (log) to run",
576 "scale score by [f]ractionality or [i]mpact on farkasproof",
int SCIPgetNObjVars(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real 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 SCIPincludeHeurFarkasdiving(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool ispublic, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)),)
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
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_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
int SCIPheurGetNDivesets(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)
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
void SCIPsortReal(SCIP_Real *realarray, int len)
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
SCIPfreeSol(scip, &heurdata->sol))
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define DEFAULT_MAXLPITERQUOT
#define DEFAULT_SCALESCORE
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define DEFAULT_SCALETYPE
#define DEFAULT_ROOTSUCCESS
static SCIP_RETCODE checkGlobalProperties(SCIP *scip, SCIP_HEURDATA *heurdata)
#define divesetAvailableFarkasdiving
#define DEFAULT_CHECKCANDS
#define DIVESET_DIVETYPES
static SCIP_RETCODE checkDivingCandidates(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **divecandvars, int ndivecands, SCIP_Bool *success)
#define DEFAULT_MAXOBJOCC
#define DEFAULT_MINRELDEPTH
LP diving heuristic that tries to construct a Farkas-proof.
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
memory allocation routines
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for branch and bound tree
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 the branch-and-bound tree
#define SCIP_DECL_HEURINITSOL(x)
#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_DIVESETGETSCORE(x)
#define SCIP_DECL_HEUREXEC(x)
@ SCIP_DIVECONTEXT_SINGLE
enum SCIP_Retcode SCIP_RETCODE