32 #define HEUR_NAME "oneopt" 33 #define HEUR_DESC "1-opt heuristic which tries to improve setting of single integer variables" 34 #define HEUR_DISPCHAR 'b' 35 #define HEUR_PRIORITY -20000 37 #define HEUR_FREQOFS 0 38 #define HEUR_MAXDEPTH -1 39 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_AFTERNODE 40 #define HEUR_USESSUBSCIP FALSE 42 #define DEFAULT_WEIGHTEDOBJ TRUE 43 #define DEFAULT_DURINGROOT TRUE 44 #define DEFAULT_BEFOREPRESOL FALSE 45 #define DEFAULT_FORCELPCONSTRUCTION FALSE 46 #define DEFAULT_USELOOP TRUE 84 assert(subscip != NULL);
85 assert(subvars != NULL);
86 assert(subsol != NULL);
145 else if( obj < 0.0 &&
SCIPisFeasLE(scip, solval + 1.0, ub) )
155 SCIPdebugMsg(scip,
" lb:<%g> <= val:<%g> <= ub:<%g> and obj:<%g> by at most: <%g>\n", lb, solval, ub, obj, shiftval);
163 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
166 for( i = 0; i < ncolrows && shiftval > 0.0; ++i )
182 if( shiftdown == (colvals[i] > 0) )
187 if( shiftvalrow < shiftval )
189 SCIPdebugMsg(scip,
" -> The shift value had to be reduced to <%g>, because of row <%s>.\n",
191 SCIPdebugMsg(scip,
" lhs:<%g> <= act:<%g> <= rhs:<%g>, colval:<%g>\n",
195 shiftval = MIN(shiftval, shiftvalrow);
197 shiftval =
MAX(shiftval, 0.0);
227 assert(activities != NULL);
234 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
237 for( i = 0; i < ncolrows; ++i )
249 activities[rowpos] += shiftval * colvals[i];
282 assert(scip != NULL);
283 assert(subscip != NULL);
284 assert(heur != NULL);
297 for( i = 0; i < nvars; i++ )
338 SCIPwarningMessage(scip,
"unfixing parameter lp/solvefreq in subscip of oneopt heuristic\n");
345 SCIPwarningMessage(scip,
"unfixing parameter heuristics/oneopt/freq in subscip of oneopt heuristic\n");
352 SCIPwarningMessage(scip,
"unfixing parameter heuristics/oneopt/forcelpconstruction in subscip of oneopt heuristic\n");
360 SCIPwarningMessage(scip,
"unfixing parameter heuristics/oneopt/beforepresol in subscip of oneopt heuristic\n");
385 for( i = 0; i < nsubsols && !(*valid); ++i )
404 assert(
scip != NULL);
405 assert(heur != NULL);
420 assert(heur != NULL);
422 assert(
scip != NULL);
426 assert(heurdata != NULL);
444 assert(heurdata != NULL);
457 assert(heur != NULL);
472 assert(heur != NULL);
473 assert(
scip != NULL);
477 assert(heurdata != NULL);
480 heurdata->lastsolindex = -1;
514 int nsuccessfulshifts;
517 assert(heur != NULL);
518 assert(
scip != NULL);
519 assert(result != NULL);
523 assert(heurdata != NULL);
529 if( bestsol == NULL || heurdata->lastsolindex ==
SCIPsolGetIndex(bestsol) )
538 nintvars += nbinvars;
554 if( !heurdata->beforepresol )
601 nintvars += nbinvars;
618 for( i = nvars - 1; i >= 0; --i )
646 SCIPdebugMsg(
scip,
"number of bound changes (due to global bounds) = %d\n", nchgbound);
655 for( i = 0; i < nlprows; ++i )
681 SCIPdebugMsg(
scip,
"Some global bound changes were not valid in lp rows.\n");
693 nsuccessfulshifts = 0;
701 SCIPdebugMsg(
scip,
"Starting 1-opt heuristic iteration #%d\n", niterations);
707 for( i = 0; i < nintvars; i++ )
723 if( nshiftcands == shiftcandssize)
729 shiftcands[nshiftcands] = vars[i];
730 shiftvals[nshiftcands] = shiftval;
737 if( nshiftcands > 0 )
744 if( nshiftcands == 1 )
749 shiftval = shiftvals[0];
751 SCIPdebugMsg(
scip,
" Only one shiftcand found, var <%s>, which is now shifted by<%1.1f> \n",
766 if( heurdata->weightedobj )
768 for( i = 0; i < nshiftcands; ++i )
773 for( i = 0; i < nshiftcands; ++i )
781 for( i = 0; i < nshiftcands; ++i )
805 }
while( heurdata->useloop && shifted );
807 if( nsuccessfulshifts > 0 )
835 SCIPdebugMsg(
scip,
"shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
841 for( i = 0; i < nvars; ++i )
850 for( i = 0; i < nintvars; ++i )
872 SCIPwarningMessage(
scip,
"Error while solving LP in 1-opt heuristic; LP solve terminated with code <%d>\n",retstat);
907 if( heurdata->useloop )
941 assert(heur != NULL);
952 "should the objective be weighted with the potential shifting value when sorting the shifting candidates?",
956 "should the heuristic be called before and during the root node?",
960 "should the construction of the LP be forced even if LP solving is deactivated?",
964 "should the heuristic be called before presolving?",
968 "should the heuristic continue to run as long as improvements are found?",
enum SCIP_Result SCIP_RESULT
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIP_HEURTIMING_DURINGLPLOOP
#define DEFAULT_BEFOREPRESOL
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
#define DEFAULT_WEIGHTEDOBJ
Improvement heuristic that alters single variable values.
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
#define DEFAULT_DURINGROOT
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
static SCIP_RETCODE setupAndSolveSubscipOneopt(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_SOL *bestsol, SCIP_RESULT *result, SCIP_Bool *valid)
int SCIPgetNOrigVars(SCIP *scip)
#define SCIP_HEURTIMING_BEFORENODE
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
#define DEFAULT_FORCELPCONSTRUCTION
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
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)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
static SCIP_Real calcShiftVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real *activities)
#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 SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
SCIP_RETCODE SCIPsolve(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyOneopt)
const char * SCIPvarGetName(SCIP_VAR *var)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
static SCIP_RETCODE updateRowActivities(SCIP *scip, SCIP_Real *activities, SCIP_VAR *var, SCIP_Real shiftval)
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
int SCIPgetNLPRows(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEUREXITSOL(heurExitsolOneopt)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
#define SCIP_HEURTIMING_BEFOREPRESOL
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
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 SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
static SCIP_DECL_HEUREXEC(heurExecOneopt)
int SCIPgetNSols(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
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)
int SCIPgetNVars(SCIP *scip)
static SCIP_DECL_HEURINIT(heurInitOneopt)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIProwGetLPPos(SCIP_ROW *row)
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
static SCIP_DECL_HEURFREE(heurFreeOneopt)
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
static SCIP_DECL_HEURINITSOL(heurInitsolOneopt)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_RETCODE SCIPincludeHeurOneopt(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_RETCODE SCIPendDive(SCIP *scip)
#define SCIP_CALL_ABORT(x)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
int SCIPsolGetIndex(SCIP_SOL *sol)
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)
#define SCIPreallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)