31 #define HEUR_NAME "ofins" 32 #define HEUR_DESC "primal heuristic for reoptimization, objective function induced neighborhood search" 33 #define HEUR_DISPCHAR 'A' 34 #define HEUR_PRIORITY 60000 36 #define HEUR_FREQOFS 0 37 #define HEUR_MAXDEPTH 0 38 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 39 #define HEUR_USESSUBSCIP TRUE 42 #define DEFAULT_MAXNODES 5000LL 43 #define DEFAULT_MAXCHGRATE 0.50 44 #define DEFAULT_COPYCUTS TRUE 46 #define DEFAULT_MAXCHANGE 0.04 47 #define DEFAULT_MINIMPROVE 0.01 48 #define DEFAULT_ADDALLSOLS FALSE 49 #define DEFAULT_MINNODES 50LL 50 #define DEFAULT_NODESOFS 500LL 51 #define DEFAULT_NODESQUOT 0.1 52 #define DEFAULT_LPLIMFAC 2.0 55 #define EVENTHDLR_NAME "Ofins" 56 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 86 assert(eventhdlr !=
NULL);
87 assert(eventdata !=
NULL);
89 assert(event !=
NULL);
93 assert(heurdata !=
NULL);
121 assert(scip !=
NULL);
122 assert(subscip !=
NULL);
123 assert(subvars !=
NULL);
124 assert(subsol !=
NULL);
184 assert(scip !=
NULL);
185 assert(heur !=
NULL);
186 assert(heurdata !=
NULL);
187 assert(result !=
NULL);
188 assert(chgcoeffs !=
NULL);
192 SCIPdebugMsg(scip,
"+---+ Start OFINS heuristic +---+\n");
229 for( i = 0; i < nintvars; i++ )
233 fixedvars[nfixedvars] = vars[i];
250 if( eventhdlr ==
NULL )
257 for( i = 0; i < nvars; i++ )
260 assert(subvars[i] !=
NULL);
287 heurdata->nodelimit = heurdata->maxnodes;
329 SCIPwarningMessage(scip,
"Error while presolving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n",
HEUR_NAME, retcode);
341 assert(eventhdlr !=
NULL);
347 SCIPdebugMsg(scip,
"solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT
", maxnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->maxnodes);
379 for( i = 0; i < nsubvars; i++ )
403 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); i++ )
412 SCIPstatisticPrintf(
"%s statistic: fixed %6.3f integer variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT
" nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT
"\n",
434 assert(scip !=
NULL);
435 assert(heur !=
NULL);
450 assert(heur !=
NULL);
451 assert(scip !=
NULL);
455 assert(heurdata !=
NULL);
476 assert( heur !=
NULL );
477 assert( scip !=
NULL );
478 assert( result !=
NULL );
488 assert( heurdata !=
NULL );
509 nstallnodes += heurdata->nodesofs;
512 nstallnodes =
MIN(nstallnodes, heurdata->maxnodes);
515 if( nstallnodes < heurdata->minnodes )
517 SCIPdebugMsg(scip,
"skipping OFINS: nstallnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
528 for( v = 0; v < nvars; v++ )
555 frac =
MIN(1, newcoefabs);
557 frac =
MIN(1, oldcoefabs);
564 frac = 1.0 -
MIN(newcoefabs, oldcoefabs)/
MAX(newcoefabs, oldcoefabs);
575 if( frac > heurdata->maxchange )
581 chgcoeffs[v] =
FALSE;
584 SCIPdebugMsg(scip,
"%d (rate %.4f) changed coefficients\n", nchgcoefs, nchgcoefs/((
SCIP_Real)nvars));
594 if( nchgcoefs/((
SCIP_Real)nvars) > heurdata->maxchangerate )
620 assert(heurdata !=
NULL);
627 assert(heur !=
NULL);
636 "maximum number of nodes to regard in the subproblem",
640 "minimum number of nodes required to start the subproblem",
644 "maximal rate of changed coefficients",
648 "maximal rate of change per coefficient to get fixed",
652 "should all active cuts from cutpool be copied to constraints in subproblem?",
656 "should all subproblem solutions be added to the original SCIP?",
660 "number of nodes added to the contingent of the total nodes",
664 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
668 "factor by which RENS should at least improve the incumbent",
672 "factor by which the limit on the number of LP depends on the node limit",
enum SCIP_Result SCIP_RESULT
int SCIPgetNIntVars(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
#define SCIP_EVENTTYPE_LPSOLVED
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
static SCIP_DECL_HEURCOPY(heurCopyOfins)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
static SCIP_DECL_HEURFREE(heurFreeOfins)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
int SCIPgetNOrigVars(SCIP *scip)
static SCIP_DECL_EVENTEXEC(eventExecOfins)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
#define DEFAULT_NODESQUOT
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_RETCODE SCIPincludeHeurOfins(SCIP *scip)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEUREXEC(heurExecOfins)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPvarGetProbindex(SCIP_VAR *var)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIPfreeBlockMemory(scip, ptr)
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)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcreate(SCIP **scip)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPsolve(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
#define SCIPfreeBufferArrayNull(scip, ptr)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
struct SCIP_EventData SCIP_EVENTDATA
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_SOL * SCIPgetReoptLastOptSol(SCIP *scip)
#define SCIPstatisticPrintf
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_Bool SCIPhasPrimalRay(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
public data structures and miscellaneous methods
#define DEFAULT_ADDALLSOLS
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
int SCIPgetNImplVars(SCIP *scip)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
#define DEFAULT_MINIMPROVE
SCIP_RETCODE SCIPprintRay(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
enum SCIP_Status SCIP_STATUS
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPtrySolFree(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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
int SCIPgetNSols(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPgetReoptOldObjCoef(SCIP *scip, SCIP_VAR *var, int run, SCIP_Real *objcoef)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
int SCIPgetNReoptRuns(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_RETCODE SCIPupdatePrimalRay(SCIP *scip, SCIP_SOL *primalray)
SCIP_Bool SCIPisStopped(SCIP *scip)
#define DEFAULT_MAXCHGRATE
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_CALL_ABORT(x)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
#define DEFAULT_MAXCHANGE
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
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 SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_Real SCIPgetPrimalRayVal(SCIP *scip, SCIP_VAR *var)
static SCIP_RETCODE applyOfins(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_Bool *chgcoeffs)
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_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
OFINS - Objective Function Induced Neighborhood Search - a primal heuristic for reoptimization.