heur_oneopt.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 /* @note If the heuristic runs in the root node, the timing is changed to (SCIP_HEURTIMING_DURINGLPLOOP |
62 #define DEFAULT_WEIGHTEDOBJ TRUE /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */
63 #define DEFAULT_DURINGROOT TRUE /**< should the heuristic be called before and during the root node? */
65 #define DEFAULT_FORCELPCONSTRUCTION FALSE /**< should the construction of the LP be forced even if LP solving is deactivated? */
66 #define DEFAULT_USELOOP TRUE /**< should the heuristic continue to run as long as improvements are found? */
75 SCIP_Bool weightedobj; /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */
77 SCIP_Bool forcelpconstruction;/**< should the construction of the LP be forced even if LP solving is deactivated? */
79 SCIP_Bool useloop; /**< should the heuristic continue to run as long as improvements are found? */
126 SCIPdebugMsg(scip, "Try to shift %s variable <%s> with\n", shiftdown ? "down" : "up", SCIPvarGetName(var) );
127 SCIPdebugMsg(scip, " lb:<%g> <= val:<%g> <= ub:<%g> and obj:<%g> by at most: <%g>\n", lb, solval, ub, obj, shiftval);
168 /* shiftvalrow might be negative, if we detected infeasibility -> make sure that shiftval is >= 0 */
262 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "oneopt", TRUE, FALSE, FALSE, TRUE, valid) );
271 SCIP_CALL( SCIPsetSolVal(subscip, startsol, subvars[i], SCIPgetSolVal(scip, bestsol, vars[i])) );
310 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/freq in subscip of oneopt heuristic\n");
317 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/forcelpconstruction in subscip of oneopt heuristic\n");
325 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/beforepresol in subscip of oneopt heuristic\n");
336 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
345 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
393 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
405 /* if the heuristic is called at the root node, we may want to be called during the cut-and-price loop and even before the first LP solve */
412 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
527 retcode = setupAndSolveSubscipOneopt(scip, subscip, heur, vars, subvars, bestsol, result, &valid);
542 if( heurtiming == SCIP_HEURTIMING_BEFORENODE && (SCIPhasCurrentNodeLP(scip) || heurdata->forcelpconstruction) )
548 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
592 SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to lb %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, lb);
600 SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to ub %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, ub);
624 if( SCIPisFeasLT(scip, activities[i], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, activities[i], SCIProwGetRhs(row)) )
628 SCIPdebugMsg(scip, "row <%s> activity %g violates bounds, lhs = %g, rhs = %g\n", SCIProwGetName(row), activities[i], SCIProwGetLhs(row), SCIProwGetRhs(row));
662 /* @todo if useloop=TRUE store for each variable which constraint blocked it and only iterate over those variables
679 SCIPdebugMsg(scip, " -> Variable <%s> can be shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval);
746 assert(SCIPisFeasGE(scip, solval+shiftval, SCIPvarGetLbGlobal(var)) && SCIPisFeasLE(scip, solval+shiftval, SCIPvarGetUbGlobal(var)));
751 SCIPdebugMsg(scip, " -> Variable <%s> is now shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval);
767 /* if the problem is a pure IP, try to install the solution, if it is a MIP, solve LP again to set the continuous
770 if( nvars == nintvars || !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
774 /* since we ignore local rows, we cannot guarantee their feasibility and have to set the checklprows flag to
793 SCIPdebugMsg(scip, "shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
820 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
822 /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE, say, rather solve the NLP instead of the LP */
823 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
824 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
830 SCIPwarningMessage(scip, "Error while solving LP in 1-opt heuristic; LP solve terminated with code <%d>\n",retstat);
836 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
862 /* heuristic should not rerun on this incumbent because the heuristic loop finishes only after no further
910 "should the objective be weighted with the potential shifting value when sorting the shifting candidates?",
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:557
Definition: type_result.h:33
Definition: type_result.h:47
Definition: type_result.h:34
Improvement heuristic that alters single variable values.
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
public methods for SCIP parameter handling
Definition: struct_scip.h:59
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
public methods for memory management
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
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)
Definition: heur_oneopt.c:235
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
public solving methods
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2152
Definition: struct_var.h:198
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1396
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2359
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:916
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3200
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2814
public methods for problem variables
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)
Definition: scip_param.c:48
static SCIP_Real calcShiftVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real *activities)
Definition: heur_oneopt.c:89
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2618
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
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)
Definition: scip_sol.c:3125
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
public methods for numerical tolerances
Definition: struct_lp.h:126
public methods for querying solving statistics
Definition: struct_sol.h:64
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)
Definition: scip_heur.c:108
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:610
Definition: struct_misc.h:128
Definition: type_result.h:35
Definition: type_paramset.h:54
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:540
Definition: type_var.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1469
static SCIP_RETCODE updateRowActivities(SCIP *scip, SCIP_Real *activities, SCIP_VAR *var, SCIP_Real shiftval)
Definition: heur_oneopt.c:185
Definition: type_retcode.h:33
public methods for problem copies
SCIP_EXPORT void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
public methods for primal CIP solutions
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
Definition: struct_heur.h:88
Definition: type_lp.h:34
public methods for primal heuristic plugins and divesets
public data structures and miscellaneous methods
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
Definition: struct_lp.h:192
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2391
public methods for LP management
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:3874
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
public methods for the LP relaxation, rows and columns
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
methods for sorting joint arrays of various types
general public methods
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:435
public methods for solutions
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
public methods for message handling
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
public methods for primal heuristics
Definition: objbenders.h:33
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)
Definition: scip_sol.c:3231
public methods for global and local (sub)problems
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2084
memory allocation routines