LP diving heuristic that tries to construct a Farkas-proof.
The heuristic dives into the direction of the pseudosolution, i.e., variables get rounded towards their best bound w.r.t there objective coefficient. This strategy is twofold, if a feasible solution is found the solution has potentially a very good objective value; on the other hand, the left-hand side of a potential Farkas-proof \(y^Tb - y^TA{l',u'} > 0\) (i.e., infeasibility proof) gets increased, where \(l',u'\) are the local bounds. The contribution of each variable \(x_i\) to the Farkas-proof can be approximated by \(c_i = y^TA_i\) because we only dive on basic variables with reduced costs \(c_i - y^TA_i = 0\).
Definition in file heur_farkasdiving.c.
#include "blockmemshell/memory.h"
#include "scip/heur_farkasdiving.h"
#include "scip/heuristics.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_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_tree.h"
#include <string.h>
Go to the source code of this file.
Functions | |
static SCIP_RETCODE | checkDivingCandidates (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **divecandvars, int ndivecands, SCIP_Bool *success) |
static SCIP_RETCODE | checkGlobalProperties (SCIP *scip, SCIP_HEURDATA *heurdata) |
static | SCIP_DECL_HEURCOPY (heurCopyFarkasdiving) |
static | SCIP_DECL_HEURFREE (heurFreeFarkasdiving) |
static | SCIP_DECL_HEURINIT (heurInitFarkasdiving) |
static | SCIP_DECL_HEUREXIT (heurExitFarkasdiving) |
static | SCIP_DECL_HEURINITSOL (heurInitsolFarkasdiving) |
static | SCIP_DECL_HEUREXEC (heurExecFarkasdiving) |
static | SCIP_DECL_DIVESETGETSCORE (divesetGetScoreFarkasdiving) |
SCIP_RETCODE | SCIPincludeHeurFarkasdiving (SCIP *scip) |
#define HEUR_NAME "farkasdiving" |
Definition at line 62 of file heur_farkasdiving.c.
#define HEUR_DESC "LP diving heuristic that tries to construct a Farkas-proof" |
Definition at line 63 of file heur_farkasdiving.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING |
Definition at line 64 of file heur_farkasdiving.c.
#define HEUR_PRIORITY -900000 |
Definition at line 65 of file heur_farkasdiving.c.
#define HEUR_FREQ 10 |
Definition at line 66 of file heur_farkasdiving.c.
#define HEUR_FREQOFS 0 |
Definition at line 67 of file heur_farkasdiving.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 68 of file heur_farkasdiving.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 69 of file heur_farkasdiving.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 70 of file heur_farkasdiving.c.
#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE |
bit mask that represents all supported dive types
Definition at line 71 of file heur_farkasdiving.c.
#define DIVESET_ISPUBLIC FALSE |
is this dive set publicly available (ie., can be used by other primal heuristics?)
Definition at line 72 of file heur_farkasdiving.c.
#define DEFAULT_MINRELDEPTH 0.0 |
minimal relative depth to start diving
Definition at line 79 of file heur_farkasdiving.c.
#define DEFAULT_MAXRELDEPTH 1.0 |
maximal relative depth to start diving
Definition at line 80 of file heur_farkasdiving.c.
#define DEFAULT_MAXLPITERQUOT 0.05 |
maximal fraction of diving LP iterations compared to node LP iterations
Definition at line 81 of file heur_farkasdiving.c.
#define DEFAULT_MAXLPITEROFS 1000 |
additional number of allowed LP iterations
Definition at line 82 of file heur_farkasdiving.c.
#define DEFAULT_MAXDIVEUBQUOT 0.8 |
maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 83 of file heur_farkasdiving.c.
#define DEFAULT_MAXDIVEAVGQUOT 0.0 |
maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 85 of file heur_farkasdiving.c.
#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 |
maximal UBQUOT when no solution was found yet (0.0: no limit)
Definition at line 87 of file heur_farkasdiving.c.
#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 |
maximal AVGQUOT when no solution was found yet (0.0: no limit)
Definition at line 88 of file heur_farkasdiving.c.
#define DEFAULT_BACKTRACK TRUE |
use one level of backtracking if infeasibility is encountered?
Definition at line 89 of file heur_farkasdiving.c.
#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 |
percentage of immediate domain changes during probing to trigger LP resolve
Definition at line 90 of file heur_farkasdiving.c.
#define DEFAULT_LPSOLVEFREQ 1 |
LP solve frequency for diving heuristics
Definition at line 91 of file heur_farkasdiving.c.
#define DEFAULT_ONLYLPBRANCHCANDS FALSE |
should only LP branching candidates be considered instead of the slower but more general constraint handler diving variable selection?
Definition at line 92 of file heur_farkasdiving.c.
#define DEFAULT_RANDSEED 151 |
initial seed for random number generation
Definition at line 94 of file heur_farkasdiving.c.
#define DEFAULT_MAXOBJOCC 1.0 |
maximal occurance factor of an objective coefficient
Definition at line 96 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
#define DEFAULT_OBJDYN 0.0001 |
minimal objective dynamism (log)
Definition at line 97 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
#define DEFAULT_CHECKCANDS FALSE |
should diving candidates be checked before running?
Definition at line 98 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
#define DEFAULT_SCALESCORE TRUE |
should the score be scaled?
Definition at line 99 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
#define DEFAULT_ROOTSUCCESS TRUE |
should the heuristic only run within the tree if at least one solution was found at the root node?
Definition at line 100 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
#define DEFAULT_SCALETYPE 'i' |
scale score by [f]ractionality or [i]mpact on farkasproof
Definition at line 102 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
#define MIN_RAND 1e-06 |
Definition at line 446 of file heur_farkasdiving.c.
#define MAX_RAND 1e-05 |
Definition at line 447 of file heur_farkasdiving.c.
#define divesetAvailableFarkasdiving NULL |
Definition at line 521 of file heur_farkasdiving.c.
Referenced by SCIPincludeHeurFarkasdiving().
|
static |
check whether the diving candidates fulfill requirements
scip | SCIP data structure |
heurdata | heuristic data |
divecandvars | diving candidates to check |
ndivecands | number of diving candidates |
success | pointer to store whether the check was successfull |
Definition at line 122 of file heur_farkasdiving.c.
References assert(), FALSE, heurdata, i, NULL, obj, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetNObjVars(), SCIPisGT(), SCIPisZero(), SCIPnodeGetNumber(), SCIPsortReal(), SCIPvarGetObj(), and TRUE.
Referenced by checkGlobalProperties(), and SCIP_DECL_HEUREXEC().
|
static |
check whether the objective functions has nonzero coefficients corresponding to binary and integer variables
scip | SCIP data structure |
heurdata | heuristic data |
Definition at line 250 of file heur_farkasdiving.c.
References assert(), checkDivingCandidates(), heurdata, nbinvars, nintvars, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetVars(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 286 of file heur_farkasdiving.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurFarkasdiving().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 300 of file heur_farkasdiving.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 321 of file heur_farkasdiving.c.
References assert(), FALSE, HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPheurGetData(), and SCIPheurGetName().
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 344 of file heur_farkasdiving.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, 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 363 of file heur_farkasdiving.c.
References assert(), FALSE, HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().
|
static |
execution method of primal heuristic
Definition at line 383 of file heur_farkasdiving.c.
References assert(), checkDivingCandidates(), checkGlobalProperties(), diveset, FALSE, heurdata, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_DIVECONTEXT_SINGLE, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPdivesetGetNSols(), SCIPgetDepth(), SCIPgetLPBranchCands(), SCIPgetLPSolstat(), SCIPheurGetData(), SCIPheurGetDivesets(), SCIPheurGetNDivesets(), SCIPperformGenericDivingAlgorithm(), and TRUE.
|
static |
calculate score and preferred rounding direction for the candidate variable
Definition at line 451 of file heur_farkasdiving.c.
References assert(), diveset, FALSE, heurdata, MAX_RAND, MIN_RAND, NULL, obj, REALABS, roundup, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPceil(), SCIPdivesetGetHeur(), SCIPdivesetGetRandnumgen(), SCIPfloor(), SCIPheurGetData(), SCIPisEQ(), SCIPisNegative(), SCIPisPositive(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.