LNS heuristic that tries to randomly mutate the incumbent solution.
Definition in file heur_mutation.c.
#include "blockmemshell/memory.h"
#include "scip/heuristics.h"
#include "scip/heur_mutation.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "mutation" |
#define | HEUR_DESC "mutation heuristic randomly fixing variables" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -1103010 |
#define | HEUR_FREQ -1 |
#define | HEUR_FREQOFS 8 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_NODESOFS 500 |
#define | DEFAULT_MAXNODES 5000 |
#define | DEFAULT_MINIMPROVE 0.01 |
#define | DEFAULT_MINNODES 500 |
#define | DEFAULT_MINFIXINGRATE 0.8 |
#define | DEFAULT_NODESQUOT 0.1 |
#define | DEFAULT_NWAITINGNODES 200 |
#define | DEFAULT_USELPROWS FALSE |
#define | DEFAULT_COPYCUTS TRUE |
#define | DEFAULT_BESTSOLLIMIT -1 |
#define | DEFAULT_USEUCT FALSE |
#define | DEFAULT_RANDSEED 19 |
Functions | |
static SCIP_RETCODE | determineVariableFixings (SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, SCIP_Real minfixingrate, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool *success) |
static SCIP_RETCODE | setupAndSolveSubscipMutation (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Longint nsubnodes, SCIP_RESULT *result) |
static | SCIP_DECL_HEURCOPY (heurCopyMutation) |
static | SCIP_DECL_HEURFREE (heurFreeMutation) |
static | SCIP_DECL_HEURINIT (heurInitMutation) |
static | SCIP_DECL_HEUREXIT (heurExitMutation) |
static | SCIP_DECL_HEUREXEC (heurExecMutation) |
SCIP_RETCODE | SCIPincludeHeurMutation (SCIP *scip) |
#define HEUR_NAME "mutation" |
Definition at line 58 of file heur_mutation.c.
#define HEUR_DESC "mutation heuristic randomly fixing variables" |
Definition at line 59 of file heur_mutation.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 60 of file heur_mutation.c.
#define HEUR_PRIORITY -1103010 |
Definition at line 61 of file heur_mutation.c.
#define HEUR_FREQ -1 |
Definition at line 62 of file heur_mutation.c.
#define HEUR_FREQOFS 8 |
Definition at line 63 of file heur_mutation.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 64 of file heur_mutation.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 65 of file heur_mutation.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 66 of file heur_mutation.c.
#define DEFAULT_NODESOFS 500 |
number of nodes added to the contingent of the total nodes
Definition at line 68 of file heur_mutation.c.
#define DEFAULT_MAXNODES 5000 |
maximum number of nodes to regard in the subproblem
Definition at line 69 of file heur_mutation.c.
#define DEFAULT_MINIMPROVE 0.01 |
factor by which Mutation should at least improve the incumbent
Definition at line 70 of file heur_mutation.c.
#define DEFAULT_MINNODES 500 |
minimum number of nodes to regard in the subproblem
Definition at line 71 of file heur_mutation.c.
#define DEFAULT_MINFIXINGRATE 0.8 |
minimum percentage of integer variables that have to be fixed
Definition at line 72 of file heur_mutation.c.
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 73 of file heur_mutation.c.
#define DEFAULT_NWAITINGNODES 200 |
number of nodes without incumbent change that heuristic should wait
Definition at line 74 of file heur_mutation.c.
#define DEFAULT_USELPROWS FALSE |
should subproblem be created out of the rows in the LP rows, otherwise, the copy constructors of the constraints handlers are used
Definition at line 75 of file heur_mutation.c.
#define DEFAULT_COPYCUTS TRUE |
if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool of the original scip be copied to constraints of the subscip
Definition at line 77 of file heur_mutation.c.
#define DEFAULT_BESTSOLLIMIT -1 |
limit on number of improving incumbent solutions in sub-CIP
Definition at line 79 of file heur_mutation.c.
#define DEFAULT_USEUCT FALSE |
should uct node selection be used at the beginning of the search?
Definition at line 80 of file heur_mutation.c.
#define DEFAULT_RANDSEED 19 |
initial random seed
Definition at line 81 of file heur_mutation.c.
|
static |
determine variables and values which should be fixed in the mutation subproblem
scip | original SCIP data structure |
fixedvars | array to store the variables that should be fixed in the subproblem |
fixedvals | array to store the fixing values to fix variables in the subproblem |
nfixedvars | pointer to store the number of variables that should be fixed |
minfixingrate | percentage of integer variables that have to be fixed |
randnumgen | random number generator |
success | used to store whether the creation of the subproblem worked |
Definition at line 113 of file heur_mutation.c.
References assert(), BMScopyMemoryArray, FALSE, i, nbinvars, nintvars, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPrandomPermuteArray(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), sol, TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
setup and solve mutation sub-SCIP
scip | SCIP data structure |
subscip | sub-SCIP data structure |
heur | mutation heuristic |
fixedvars | array to store the variables that should be fixed in the subproblem |
fixedvals | array to store the fixing values to fix variables in the subproblem |
nfixedvars | the number of variables that should be fixed |
nsubnodes | node limit for the subproblem |
result | pointer to store the result |
Definition at line 195 of file heur_mutation.c.
References assert(), cutoff, FALSE, heurdata, i, MIN, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetLowerbound(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetUpperbound(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPisInfinity(), SCIPisParamFixed(), SCIPmergeVariableStatistics(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPtranslateSubSols(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 360 of file heur_mutation.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurMutation().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 374 of file heur_mutation.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 394 of file heur_mutation.c.
References assert(), DEFAULT_RANDSEED, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPheurGetData(), and TRUE.
|
static |
deinitialization method of primal heuristic
Definition at line 417 of file heur_mutation.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 436 of file heur_mutation.c.
References assert(), determineVariableFixings(), heurdata, MIN, nbinvars, nintvars, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcheckCopyLimits(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolNodenum(), SCIPgetVarsData(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisStopped(), SCIPsolIsOriginal(), and setupAndSolveSubscipMutation().