31 #define HEUR_NAME "rins" 32 #define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape" 33 #define HEUR_DISPCHAR 'N' 34 #define HEUR_PRIORITY -1101000 36 #define HEUR_FREQOFS 0 37 #define HEUR_MAXDEPTH -1 38 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 39 #define HEUR_USESSUBSCIP TRUE 41 #define DEFAULT_NODESOFS 500 42 #define DEFAULT_MAXNODES 5000 43 #define DEFAULT_MINNODES 50 44 #define DEFAULT_MINIMPROVE 0.01 45 #define DEFAULT_MINFIXINGRATE 0.3 46 #define DEFAULT_NODESQUOT 0.1 47 #define DEFAULT_LPLIMFAC 2.0 48 #define DEFAULT_NWAITINGNODES 200 49 #define DEFAULT_USELPROWS FALSE 51 #define DEFAULT_COPYCUTS TRUE 54 #define DEFAULT_USEUCT FALSE 57 #define EVENTHDLR_NAME "Rins" 58 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 114 assert(fixedvals !=
NULL);
115 assert(fixedvars !=
NULL);
116 assert(nfixedvars !=
NULL);
121 assert(bestsol !=
NULL);
124 assert(fixedvarssize >= nbinvars + nintvars);
127 for( i = 0; i < nbinvars + nintvars; i++ )
140 fixedvars[fixingcounter] = vars[i];
141 fixedvals[fixingcounter] = solval;
147 *nfixedvars = fixingcounter;
150 if( fixingcounter == nbinvars + nintvars )
159 if( fixingrate < minfixingrate )
186 assert( scip !=
NULL );
187 assert( subscip !=
NULL );
188 assert( subvars !=
NULL );
189 assert( subsol !=
NULL );
226 assert(eventhdlr !=
NULL);
227 assert(eventdata !=
NULL);
229 assert(event !=
NULL);
233 assert(heurdata !=
NULL);
255 assert(heur !=
NULL);
270 assert( heur !=
NULL );
275 assert( heurdata !=
NULL );
291 assert( heur !=
NULL );
296 assert( heurdata !=
NULL );
299 heurdata->usednodes = 0;
331 assert( heur !=
NULL );
333 assert( result !=
NULL );
344 assert( heurdata !=
NULL );
371 nnodes += heurdata->nodesofs;
374 nnodes -= heurdata->usednodes;
375 nnodes =
MIN(nnodes, heurdata->maxnodes);
378 if( nnodes < heurdata->minnodes )
384 if( nbinvars == 0 && nintvars == 0 )
411 assert(nfixedvars > 0 && nfixedvars < nbinvars + nintvars);
415 SCIPdebugMsg(
scip,
"RINS heuristic fixes %d out of %d binary+integer variables\n", nfixedvars, nbinvars + nintvars);
423 heurdata->uselprows, heurdata->copycuts, &success,
NULL) );
428 if( eventhdlr ==
NULL )
436 for( i = 0; i < nvars; i++ )
457 heurdata->nodelimit =
nnodes;
528 cutoff =
MIN(upperbound, cutoff);
564 for( i = 0; i < nsubsols && !success; ++i )
602 assert(heur !=
NULL);
611 "number of nodes added to the contingent of the total nodes",
615 "maximum number of nodes to regard in the subproblem",
619 "minimum number of nodes required to start the subproblem",
623 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
627 "number of nodes without incumbent change that heuristic should wait",
631 "factor by which " HEUR_NAME " should at least improve the incumbent",
635 "minimum percentage of integer variables that have to be fixed",
639 "factor by which the limit on the number of LP depends on the node limit",
643 "should subproblem be created out of the rows in the LP rows?",
647 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
651 "should uct node selection be used at the beginning of the search?",
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
#define SCIP_EVENTTYPE_LPSOLVED
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEUREXEC(heurExecRins)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
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 SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
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)
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 SCIPprintStatistics(SCIP *scip, FILE *file)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
#define DEFAULT_MINIMPROVE
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)))
#define DEFAULT_USELPROWS
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
struct SCIP_EventData SCIP_EVENTDATA
SCIP_RETCODE SCIPincludeHeurRins(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyRins)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define DEFAULT_MINFIXINGRATE
static SCIP_RETCODE determineFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, SCIP_Real minfixingrate, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
#define DEFAULT_NWAITINGNODES
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
LNS heuristic that combines the incumbent with the LP optimum.
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)
int SCIPgetNSols(SCIP *scip)
static SCIP_DECL_EVENTEXEC(eventExecRins)
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURINIT(heurInitRins)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
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_Bool SCIPisStopped(SCIP *scip)
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_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPsumepsilon(SCIP *scip)
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)
static SCIP_DECL_HEURFREE(heurFreeRins)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
#define DEFAULT_NODESQUOT
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_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 SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)