LNS heuristic that finds the optimal rounding to a given point.
Definition in file heur_rens.c.
#include "blockmemshell/memory.h"
#include "scip/heuristics.h"
#include "scip/heur_rens.h"
#include "scip/pub_event.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_event.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_nlpi.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "rens" |
#define | HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -1100000 |
#define | HEUR_FREQ 0 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_BINARYBOUNDS TRUE /* should general integers get binary bounds [floor(.),ceil(.)] ? */ |
#define | DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINFIXINGRATE 0.5 /* minimum percentage of integer variables that have to be fixed */ |
#define | DEFAULT_MINIMPROVE 0.01 /* factor by which RENS should at least improve the incumbent */ |
#define | DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
#define | DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
#define | DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
#define | DEFAULT_STARTSOL 'l' /* solution that is used for fixing values */ |
#define | STARTSOL_CHOICES "nl" /* possible values for startsol ('l'p relaxation, 'n'lp relaxation) */ |
#define | DEFAULT_USELPROWS |
#define | DEFAULT_COPYCUTS |
#define | DEFAULT_EXTRATIME |
#define | DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */ |
#define | DEFAULT_FULLSCALE |
#define | DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ |
#define | DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
#define | EVENTHDLR_NAME "Rens" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Functions | |
static SCIP_RETCODE | computeFixingrate (SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, SCIP_Real minfixingrate, char *startsol, SCIP_Real *fixingrate, SCIP_Bool *success) |
static SCIP_RETCODE | restrictToBinaryBounds (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, char startsol) |
static | SCIP_DECL_EVENTEXEC (eventExecRens) |
static SCIP_RETCODE | setupAndSolveSubscip (SCIP *scip, SCIP *subscip, SCIP_RESULT *result, SCIP_HEUR *heur, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Real intfixingrate, SCIP_Real minfixingrate, SCIP_Real minimprove, SCIP_Longint maxnodes, SCIP_Longint nstallnodes, char startsol, SCIP_Bool binarybounds, SCIP_Bool uselprows) |
SCIP_RETCODE | SCIPapplyRens (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minfixingrate, SCIP_Real minimprove, SCIP_Longint maxnodes, SCIP_Longint nstallnodes, char startsol, SCIP_Bool binarybounds, SCIP_Bool uselprows) |
static | SCIP_DECL_HEURCOPY (heurCopyRens) |
static | SCIP_DECL_HEURFREE (heurFreeRens) |
static | SCIP_DECL_HEURINIT (heurInitRens) |
static | SCIP_DECL_HEUREXEC (heurExecRens) |
SCIP_RETCODE | SCIPincludeHeurRens (SCIP *scip) |
#define HEUR_NAME "rens" |
Definition at line 65 of file heur_rens.c.
#define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum" |
Definition at line 66 of file heur_rens.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 67 of file heur_rens.c.
#define HEUR_PRIORITY -1100000 |
Definition at line 68 of file heur_rens.c.
#define HEUR_FREQ 0 |
Definition at line 69 of file heur_rens.c.
#define HEUR_FREQOFS 0 |
Definition at line 70 of file heur_rens.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 71 of file heur_rens.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 72 of file heur_rens.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 73 of file heur_rens.c.
#define DEFAULT_BINARYBOUNDS TRUE /* should general integers get binary bounds [floor(.),ceil(.)] ? */ |
Definition at line 76 of file heur_rens.c.
#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
Definition at line 77 of file heur_rens.c.
#define DEFAULT_MINFIXINGRATE 0.5 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 78 of file heur_rens.c.
#define DEFAULT_MINIMPROVE 0.01 /* factor by which RENS should at least improve the incumbent */ |
Definition at line 79 of file heur_rens.c.
#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
Definition at line 80 of file heur_rens.c.
#define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
Definition at line 81 of file heur_rens.c.
#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 82 of file heur_rens.c.
#define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 83 of file heur_rens.c.
#define DEFAULT_STARTSOL 'l' /* solution that is used for fixing values */ |
Definition at line 84 of file heur_rens.c.
#define STARTSOL_CHOICES "nl" /* possible values for startsol ('l'p relaxation, 'n'lp relaxation) */ |
Definition at line 85 of file heur_rens.c.
#define DEFAULT_USELPROWS |
Definition at line 86 of file heur_rens.c.
#define DEFAULT_COPYCUTS |
Definition at line 87 of file heur_rens.c.
#define DEFAULT_EXTRATIME |
Definition at line 88 of file heur_rens.c.
#define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */ |
Definition at line 89 of file heur_rens.c.
#define DEFAULT_FULLSCALE |
Definition at line 91 of file heur_rens.c.
#define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 92 of file heur_rens.c.
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 93 of file heur_rens.c.
#define EVENTHDLR_NAME "Rens" |
Definition at line 96 of file heur_rens.c.
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 97 of file heur_rens.c.
|
static |
compute the number of initial fixings and check whether the fixing rate exceeds the minimum fixing rate
scip | SCIP data structure |
fixedvars | array to store source SCIP variables whose copies should be fixed in the sub-SCIP |
fixedvals | array to store solution values for variable fixing |
nfixedvars | pointer to store the number of fixed variables |
fixedvarssize | size of the arrays to store fixing variables |
minfixingrate | percentage of integer variables that have to be fixed |
startsol | pointer to solution used for fixing values ('l'p relaxation, 'n'lp relaxation) |
fixingrate | percentage of integers that get actually fixed |
success | pointer to store whether minimum fixingrate is exceeded |
Definition at line 137 of file heur_rens.c.
References assert(), FALSE, i, MAX, nbinvars, nintvars, NULL, SCIP_Bool, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPfloor(), SCIPgetNLPSolstat(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisNLPConstructed(), SCIPsetNLPInitialGuessSol(), SCIPsolveNLP, SCIPvarGetLPSol(), SCIPvarGetNLPSol(), and vars.
|
static |
fixes bounds of unfixed integer variables to binary bounds
scip | original SCIP data structure |
subscip | SCIP data structure for the subproblem |
subvars | the variables of the subproblem |
startsol | solution used for fixing values ('l'p relaxation, 'n'lp relaxation) |
Definition at line 244 of file heur_rens.c.
|
static |
Definition at line 311 of file heur_rens.c.
References assert(), EVENTHDLR_NAME, heurdata, NULL, SCIP_EVENTTYPE_LPSOLVED, SCIP_LONGINT_FORMAT, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), and SCIPgetNLPs().
|
static |
setup and solve the RENS sub-SCIP
scip | SCIP data structure |
subscip | sub SCIP data structure |
result | result pointer |
heur | heuristic data structure |
fixedvars | array of variables that should be fixed |
fixedvals | array of fixing values |
nfixedvars | number of variables that should be fixed |
intfixingrate | percentage of integer variables fixed |
minfixingrate | minimum percentage of integer variables that have to be fixed |
minimprove | factor by which RENS should at least improve the incumbent |
maxnodes | maximum number of nodes for the subproblem |
nstallnodes | number of stalling nodes for the subproblem |
startsol | solution used for fixing values ('l'p relaxation, 'n'lp relaxation) |
binarybounds | should general integers get binary bounds [floor(.),ceil(.)]? |
uselprows | should subproblem be created out of the rows in the LP rows? |
Definition at line 336 of file heur_rens.c.
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 685 of file heur_rens.c.
References assert(), HEUR_NAME, NULL, and SCIPheurGetName().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 699 of file heur_rens.c.
References SCIP_OKAY.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 719 of file heur_rens.c.
|
static |
execution method of primal heuristic
Definition at line 739 of file heur_rens.c.