Detailed Description
Extreme Point RINS.
Definition in file heur_xprins.c.
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "heur_xprins.h"
#include "gcg.h"
#include "scip/scip.h"
#include "scip/misc.h"
#include "scip/scipdefplugins.h"
Go to the source code of this file.
Data Structures | |
struct | SCIP_HeurData |
Macros | |
#define | HEUR_NAME "xprins" |
#define | HEUR_DESC "Extreme Point RINS" |
#define | HEUR_DISPCHAR 'Y' |
#define | HEUR_PRIORITY -1100600 |
#define | HEUR_FREQ 0 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_EQUALITYRATE 0.5 |
#define | DEFAULT_MAXNODES 1000LL |
#define | DEFAULT_MINIMPROVE 0.01 |
#define | DEFAULT_MINNODES 200LL |
#define | DEFAULT_MINFIXINGRATE 0.4 |
#define | DEFAULT_NODESOFS 200LL |
#define | DEFAULT_NODESQUOT 0.1 |
#define | DEFAULT_NUSEDPTS -1 |
#define | DEFAULT_RANDOMIZATION FALSE |
#define | DEFAULT_COPYCUTS TRUE |
#define | DEFAULT_RANDSEED 7 |
Functions | |
static SCIP_RETCODE | selectExtremePoints (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, int *nactualpts, SCIP_Bool *success) |
static SCIP_RETCODE | selectExtremePointsRandomized (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, int *nactualpts, SCIP_Bool *success) |
static SCIP_RETCODE | countExtremePoints (SCIP *scip, int *selection, int nusedpts, int *nactualpts) |
static SCIP_RETCODE | setupSubproblem (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Longint nstallnodes, SCIP_Real timelimit, SCIP_Real memorylimit) |
static void | compareOneExtremePoint (SCIP *scip, SCIP_VAR *mastervar, int solblock, int *neqpts, SCIP_Bool *zeroblocks) |
static SCIP_RETCODE | compareExtremePointsToRelaxSol (SCIP *scip, int *selection, int nusedpts, int *neqpts, SCIP_Bool *zeroblocks) |
static SCIP_RETCODE | fixVariables (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, int *selection, int *nactualpts, SCIP_HEURDATA *heurdata, SCIP_Real *intfixingrate, SCIP_Real *zerofixingrate, SCIP_Bool *success) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success) |
static void | updateFailureStatistic (SCIP *scip, SCIP_HEURDATA *heurdata) |
static | SCIP_DECL_HEURFREE (heurFreeXprins) |
static | SCIP_DECL_HEURINIT (heurInitXprins) |
static | SCIP_DECL_HEUREXIT (heurExitXprins) |
static | SCIP_DECL_HEUREXEC (heurExecXprins) |
SCIP_RETCODE | SCIPincludeHeurXprins (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "xprins" |
Definition at line 47 of file heur_xprins.c.
◆ HEUR_DESC
#define HEUR_DESC "Extreme Point RINS" |
Definition at line 48 of file heur_xprins.c.
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR 'Y' |
Definition at line 49 of file heur_xprins.c.
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1100600 |
Definition at line 50 of file heur_xprins.c.
◆ HEUR_FREQ
#define HEUR_FREQ 0 |
Definition at line 51 of file heur_xprins.c.
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 52 of file heur_xprins.c.
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 53 of file heur_xprins.c.
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 54 of file heur_xprins.c.
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
Definition at line 55 of file heur_xprins.c.
◆ DEFAULT_EQUALITYRATE
#define DEFAULT_EQUALITYRATE 0.5 |
minimum percentage of coincidence of relaxation and extreme pts
Definition at line 57 of file heur_xprins.c.
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 1000LL |
maximum number of nodes to regard in the subproblem
Definition at line 58 of file heur_xprins.c.
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 |
factor by which xprins should at least improve the incumbent
Definition at line 59 of file heur_xprins.c.
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 200LL |
minimum number of nodes to regard in the subproblem
Definition at line 60 of file heur_xprins.c.
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.4 |
minimum percentage of integer variables that have to be fixed
Definition at line 61 of file heur_xprins.c.
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 200LL |
number of nodes added to the contingent of the total nodes
Definition at line 62 of file heur_xprins.c.
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 63 of file heur_xprins.c.
◆ DEFAULT_NUSEDPTS
#define DEFAULT_NUSEDPTS -1 |
number of extreme pts per block that will be taken into account (-1: all; 0: all which contribute to current relaxation solution)
Definition at line 64 of file heur_xprins.c.
◆ DEFAULT_RANDOMIZATION
#define DEFAULT_RANDOMIZATION FALSE |
should the choice which sols to take be randomized?
Definition at line 67 of file heur_xprins.c.
◆ DEFAULT_COPYCUTS
#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 68 of file heur_xprins.c.
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 7 |
initial random seed
Definition at line 71 of file heur_xprins.c.
Function Documentation
◆ selectExtremePoints()
|
static |
for each block, select extreme points (represented by mastervars) to be compared to the relaxation solution
- Parameters
-
scip original SCIP data structure heurdata primal heuristic data selection indices of selected extreme points nactualpts number of points per block that have actually been selected success pointer to store whether the process was successful
Definition at line 123 of file heur_xprins.c.
References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNIdenticalBlocks(), GCGgetNPricingprobs(), GCGmasterVarIsRay(), GCGvarGetBlock(), and GCGvarIsMaster().
Referenced by SCIP_DECL_HEUREXEC().
◆ selectExtremePointsRandomized()
|
static |
select extreme points (represented by mastervars) randomly
- Parameters
-
scip original SCIP data structure heurdata primal heuristic data selection indices of selected extreme points nactualpts number of points per block that have actually been selected success pointer to store whether the process was successful
Definition at line 362 of file heur_xprins.c.
References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGisPricingprobRelevant(), and GCGvarGetBlock().
Referenced by SCIP_DECL_HEUREXEC().
◆ countExtremePoints()
|
static |
- Parameters
-
scip original SCIP data structure selection selected extreme points the heuristic will use, or NULL nusedpts number of extreme points per block to be considered, or 0, or -1 nactualpts number of points per block that have actually been selected
Definition at line 515 of file heur_xprins.c.
References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), and GCGvarGetBlock().
Referenced by SCIP_DECL_HEUREXEC().
◆ setupSubproblem()
|
static |
initialize the subSCIP instance: copy SCIP to subSCIP, set the parameters
- Parameters
-
scip original SCIP data structure subscip SCIP data structure for the subproblem subvars the variables of the subproblem heurdata primal heuristic data nstallnodes node limit for subproblem timelimit time limit for subproblem memorylimit memory limit for subproblem
Definition at line 572 of file heur_xprins.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ compareOneExtremePoint()
|
static |
compare an extreme point (represented by a master variable) to the relaxation solution
- Parameters
-
scip original SCIP data structure mastervar master variable representing the extreme point solblock block in which the relaxation solution should be compared, or -1 if all blocks of the extreme point should be considered neqpts for each original variable, count how many extreme points share its relaxation solution value zeroblocks for each block, the information whether it would be fixed entirely to zero
Definition at line 703 of file heur_xprins.c.
References GCGgetNPricingprobs(), GCGisLinkingVarInBlock(), GCGlinkingVarGetPricingVars(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), GCGpricingVarGetNOrigvars(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), GCGvarIsMaster(), and GCGvarIsPricing().
Referenced by compareExtremePointsToRelaxSol().
◆ compareExtremePointsToRelaxSol()
|
static |
compare all selected extreme points to the relaxation solution
- Parameters
-
scip original SCIP data structure selection selected extreme points the heuristic will use, or NULL nusedpts number of extreme points per block to be considered, or 0, or -1 neqpts for each original variable, count how many extreme points share its relaxation solution value zeroblocks for each block, the information whether it would be fixed entirely to zero
Definition at line 817 of file heur_xprins.c.
References compareOneExtremePoint(), GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), and GCGvarGetBlock().
Referenced by fixVariables().
◆ fixVariables()
|
static |
fix variables; for each variable, we evaluate the percentage of extreme points in which it has the same value as in the relaxation solution and fix it if the percentage exceeds a certain value
- Parameters
-
scip original SCIP data structure subscip SCIP data structure for the subproblem subvars the variables of the subproblem selection selected extreme points the heuristic will use, or NULL nactualpts number of points per block that have actually been selected heurdata primal heuristic data intfixingrate percentage of integers that get actually fixed zerofixingrate percentage of variables fixed to zero success pointer to store whether the problem was created successfully
Definition at line 896 of file heur_xprins.c.
References compareExtremePointsToRelaxSol(), GCGgetNPricingprobs(), GCGlinkingVarGetPricingVars(), GCGoriginalVarIsLinking(), GCGvarGetBlock(), and GCGvarIsOriginal().
Referenced by SCIP_DECL_HEUREXEC().
◆ createNewSol()
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
- Parameters
-
scip original SCIP data structure subscip SCIP structure of the subproblem subvars the variables of the subproblem heur primal heuristic structure subsol solution of the subproblem success used to store whether new solution was found or not
Definition at line 1136 of file heur_xprins.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ updateFailureStatistic()
|
static |
updates heurdata after a run of crossover
- Parameters
-
scip original SCIP data structure heurdata primal heuristic data
Definition at line 1203 of file heur_xprins.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1223 of file heur_xprins.c.
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1243 of file heur_xprins.c.
References DEFAULT_RANDSEED.
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1268 of file heur_xprins.c.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 1352 of file heur_xprins.c.
References countExtremePoints(), createNewSol(), fixVariables(), GCGgetMasterprob(), GCGgetNPricingprobs(), HEUR_NAME, selectExtremePoints(), selectExtremePointsRandomized(), setupSubproblem(), and updateFailureStatistic().
◆ SCIPincludeHeurXprins()
SCIP_RETCODE SCIPincludeHeurXprins | ( | SCIP * | scip | ) |
creates the Extreme Point RINS primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 1658 of file heur_xprins.c.
References DEFAULT_COPYCUTS, DEFAULT_EQUALITYRATE, DEFAULT_MAXNODES, DEFAULT_MINFIXINGRATE, DEFAULT_MINIMPROVE, DEFAULT_MINNODES, DEFAULT_NODESOFS, DEFAULT_NODESQUOT, DEFAULT_NUSEDPTS, DEFAULT_RANDOMIZATION, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.
Referenced by SCIPincludeGcgPlugins().