Objective Feasibility Pump 2.0.
Definition in file heur_feaspump.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heur_feaspump.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.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_lp.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_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "feaspump" |
#define | HEUR_DESC "objective feasibility pump 2.0" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_OBJDIVING |
#define | HEUR_PRIORITY -1000000 |
#define | HEUR_FREQ 20 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
#define | HEUR_USESSUBSCIP FALSE |
#define | DEFAULT_MAXLPITERQUOT 0.01 |
#define | DEFAULT_MAXLPITEROFS 1000 |
#define | DEFAULT_MAXSOLS 10 |
#define | DEFAULT_MAXLOOPS 10000 |
#define | DEFAULT_MAXSTALLLOOPS 10 |
#define | DEFAULT_MINFLIPS 10 |
#define | DEFAULT_CYCLELENGTH 3 |
#define | DEFAULT_PERTURBFREQ 100 |
#define | DEFAULT_OBJFACTOR 0.1 |
#define | DEFAULT_ALPHA 1.0 |
#define | DEFAULT_ALPHADIFF 1.0 |
#define | DEFAULT_BEFORECUTS TRUE |
#define | DEFAULT_USEFP20 FALSE |
#define | DEFAULT_PERTSOLFOUND TRUE |
#define | DEFAULT_STAGE3 FALSE |
#define | DEFAULT_NEIGHBORHOODSIZE 18 |
#define | DEFAULT_COPYCUTS TRUE |
#define | MINLPITER 5000 |
#define | DEFAULT_RANDSEED 13 |
#define HEUR_NAME "feaspump" |
Definition at line 64 of file heur_feaspump.c.
#define HEUR_DESC "objective feasibility pump 2.0" |
Definition at line 65 of file heur_feaspump.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_OBJDIVING |
Definition at line 66 of file heur_feaspump.c.
#define HEUR_PRIORITY -1000000 |
Definition at line 67 of file heur_feaspump.c.
#define HEUR_FREQ 20 |
Definition at line 68 of file heur_feaspump.c.
#define HEUR_FREQOFS 0 |
Definition at line 69 of file heur_feaspump.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 70 of file heur_feaspump.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 71 of file heur_feaspump.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 72 of file heur_feaspump.c.
#define DEFAULT_MAXLPITERQUOT 0.01 |
maximal fraction of diving LP iterations compared to node LP iterations
Definition at line 74 of file heur_feaspump.c.
#define DEFAULT_MAXLPITEROFS 1000 |
additional number of allowed LP iterations
Definition at line 75 of file heur_feaspump.c.
#define DEFAULT_MAXSOLS 10 |
total number of feasible solutions found up to which heuristic is called (-1: no limit)
Definition at line 76 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump(), SCIPincludeHeurObjpscostdiving(), and SCIPincludeHeurRootsoldiving().
#define DEFAULT_MAXLOOPS 10000 |
maximal number of pumping rounds (-1: no limit)
Definition at line 78 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_MAXSTALLLOOPS 10 |
maximal number of pumping rounds without fractionality improvement (-1: no limit)
Definition at line 79 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_MINFLIPS 10 |
minimum number of random variables to flip, if a 1-cycle is encountered
Definition at line 80 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_CYCLELENGTH 3 |
maximum length of cycles to be checked explicitly in each round
Definition at line 81 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_PERTURBFREQ 100 |
number of iterations until a random perturbation is forced
Definition at line 82 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_OBJFACTOR 0.1 |
factor by which the regard of the objective is decreased in each round, 1.0 for dynamic, depending on solutions already found
Definition at line 83 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_ALPHA 1.0 |
initial weight of the objective function in the convex combination
Definition at line 85 of file heur_feaspump.c.
#define DEFAULT_ALPHADIFF 1.0 |
threshold difference for the convex parameter to perform perturbation
Definition at line 86 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_BEFORECUTS TRUE |
should the feasibility pump be called at root node before cut separation?
Definition at line 87 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump(), and SCIPincludeHeurUndercover().
#define DEFAULT_USEFP20 FALSE |
should an iterative round-and-propagate scheme be used to find the integral points?
Definition at line 88 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_PERTSOLFOUND TRUE |
should a random perturbation be performed if a feasible solution was found?
Definition at line 89 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_STAGE3 FALSE |
should we solve a local branching sub-MIP if no solution could be found?
Definition at line 90 of file heur_feaspump.c.
Referenced by SCIPincludeHeurFeaspump().
#define DEFAULT_NEIGHBORHOODSIZE 18 |
radius of the neighborhood to be searched in stage 3
Definition at line 91 of file heur_feaspump.c.
#define DEFAULT_COPYCUTS TRUE |
should all active cuts from the cutpool of the original SCIP be copied to constraints of the subscip
Definition at line 92 of file heur_feaspump.c.
#define MINLPITER 5000 |
minimal number of LP iterations allowed in each LP solving call
Definition at line 96 of file heur_feaspump.c.
Referenced by if(), SCIP_DECL_HEUREXEC(), SCIPperformGenericDivingAlgorithm(), solveLP(), and while().
#define DEFAULT_RANDSEED 13 |
initial random seed
Definition at line 98 of file heur_feaspump.c.
|
static |
scip | SCIP data structure |
probingscip | sub-SCIP data structure |
varmapfw | mapping of SCIP variables to sub-SCIP variables |
copycuts | should all active cuts from cutpool of scip copied to constraints in subscip |
success | was copying successful? |
Definition at line 135 of file heur_feaspump.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcreate(), SCIPgetDepth(), SCIPgetNVars(), SCIPhashmapCreate(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
set appropriate parameters for probing SCIP in FP2
scip | SCIP data structure |
probingscip | sub-SCIP data structure |
Definition at line 172 of file heur_feaspump.c.
References FALSE, HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
set appropriate parameters for probing SCIP in Stage 3
scip | SCIP data structure |
probingscip | sub-SCIP data structure |
Definition at line 216 of file heur_feaspump.c.
References FALSE, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPcopyLimits(), SCIPcopyParamSettings(), SCIPfindBranchrule(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
checks whether a variable is one of the currently most fractional ones
mostfracvars | sorted array of the currently most fractional variables |
mostfracvals | array of their fractionality, decreasingly sorted |
nflipcands | number of fractional variables already labeled to be flipped |
maxnflipcands | typically randomized number of maximum amount of variables to flip |
var | variable to be checked |
frac | fractional value of the variable |
Definition at line 286 of file heur_feaspump.c.
References assert(), frac, i, NULL, SCIP_Real, and var.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
set solution value in rounded solution and update objective coefficient accordingly
scip | SCIP data structure |
heurdata | heuristic data structure |
var | variable |
solval | solution value for this variable |
alpha | weight of original objective function |
scalingfactor | factor to scale the original objective function with |
Definition at line 332 of file heur_feaspump.c.
References alpha, assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjDive(), SCIPisEQ(), SCIPisFeasLE(), SCIPisIntegral(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbLocal(), and var.
Referenced by handle1Cycle(), handleCycle(), and SCIP_DECL_HEUREXEC().
|
static |
flips the roundings of the most fractional variables, if a 1-cycle was found
scip | SCIP data structure |
heurdata | data of this special heuristic |
mostfracvars | sorted array of the currently most fractional variables |
nflipcands | number of variables to flip |
alpha | factor how much the original objective is regarded |
scalingfactor | factor to scale the original objective function with |
Definition at line 374 of file heur_feaspump.c.
References alpha, assert(), heurdata, i, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), updateVariableRounding(), and var.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
flips the roundings of randomly chosen fractional variables, preferring highly fractional ones, if a longer cycle was found
scip | SCIP data structure |
heurdata | data of this special heuristic |
vars | array of all variables |
nbinandintvars | number of general integer and 0-1 variables |
alpha | factor how much the original objective is regarded |
scalingfactor | factor to scale the original objective function with |
Definition at line 420 of file heur_feaspump.c.
References alpha, assert(), frac, heurdata, i, MAX, MIN, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPfeasFrac(), SCIPfloor(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPrandomGetReal(), SCIPvarGetLPSol(), updateVariableRounding(), var, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
create the extra constraint of local branching and add it to subscip
scip | SCIP data structure of the original problem |
probingscip | SCIP data structure of the subproblem |
varmapfw | mapping of SCIP variables to sub-SCIP variables |
bestsol | SCIP solution |
neighborhoodsize | rhs for LB constraint |
Definition at line 472 of file heur_feaspump.c.
References assert(), FALSE, i, nbinvars, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPchgVarObj(), SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPhashmapGetImage(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetType(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
creates new solutions for the original problem by copying the solutions of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
varmapfw | mapping of SCIP variables to sub-SCIP variables |
heur | heuristic structure |
success | used to store whether new solution was found or not |
Definition at line 545 of file heur_feaspump.c.
References assert(), i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPhashmapGetImage(), SCIPtranslateSubSols(), and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 578 of file heur_feaspump.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurFeaspump().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 592 of file heur_feaspump.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 612 of file heur_feaspump.c.
References assert(), DEFAULT_RANDSEED, HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPcreateSol(), SCIPheurGetData(), SCIPheurGetName(), and TRUE.
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 640 of file heur_feaspump.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 664 of file heur_feaspump.c.
References assert(), heurdata, NULL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetFreqofs(), and SCIPheurSetTimingmask().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 681 of file heur_feaspump.c.
References HEUR_TIMING, SCIP_OKAY, and SCIPheurSetTimingmask().
|
static |
calculates an adjusted maximal number of LP iterations
maxnlpiterations | regular maximal number of LP iterations |
nsolsfound | total number of solutions found so far by SCIP |
nstallloops | current number of stalling rounds |
Definition at line 691 of file heur_feaspump.c.
References maxnlpiterations, nsolsfound, and SCIP_Longint.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
execution method of primal heuristic
Definition at line 710 of file heur_feaspump.c.
References addLocalBranchingConstraint(), adjustedMaxNLPIterations(), alpha, assert(), createNewSols(), FALSE, frac, handle1Cycle(), handleCycle(), HEUR_NAME, HEUR_TIMING, heurdata, i, insertFlipCand(), lperror, lpsolstat, MAX, maxnlpiterations, MIN, MINLPITER, nbinvars, ncalls, nintvars, nlpiterations, nsolsfound, NULL, nvars, objval, pseudocands, REALABS, result, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIP_STATUS_OPTIMAL, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPceil(), SCIPcheckCopyLimits(), SCIPchgVarObjDive(), SCIPcreateSol(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPendDive(), SCIPendProbing(), SCIPfeasFrac(), SCIPfixVarProbing(), SCIPfloor(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLastDivenode(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNBestSolsFound(), SCIPgetNLPBranchCands(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNPricers(), SCIPgetNSols(), SCIPgetNSolsFound(), SCIPgetObjNorm(), SCIPgetPrimalbound(), SCIPgetPseudoBranchCands(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetStage(), SCIPgetStatus(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurSetTimingmask(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPisFeasPositive(), SCIPisGE(), SCIPisInfinity(), SCIPisIntegral(), SCIPisLE(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPsetLongintParam(), SCIPsetSolVal(), SCIPsolve(), SCIPsolveDiveLP(), SCIPsortRealPtr(), SCIPstartDive(), SCIPstartProbing(), SCIPstatisticMessage, SCIPtrySol(), SCIPunlinkSol(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetTransVar(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPwarningMessage(), setupProbingSCIP(), setupSCIPparamsFP2(), setupSCIPparamsStage3(), updateVariableRounding(), valid, var, and vars.