Detailed Description
LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variables, and solves a final LP to calculate feasible values for continuous variables.
Definition in file heur_intshifting.c.
#include "blockmemshell/memory.h"
#include "scip/heur_intshifting.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.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_numerics.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "intshifting" |
#define | HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
#define | HEUR_PRIORITY -10000 |
#define | HEUR_FREQ 10 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
#define | HEUR_USESSUBSCIP FALSE |
#define | MAXSHIFTINGS 50 |
#define | WEIGHTFACTOR 1.1 |
#define | DEFAULT_RANDSEED 17 |
Functions | |
static void | updateViolations (SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldminactivity, SCIP_Real oldmaxactivity, SCIP_Real newminactivity, SCIP_Real newmaxactivity) |
static SCIP_RETCODE | updateActivities (SCIP *scip, SCIP_Real *minactivities, SCIP_Real *maxactivities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval) |
static SCIP_RETCODE | selectShifting (SCIP *scip, SCIP_SOL *sol, SCIP_ROW *row, SCIP_Real rowactivity, int direction, SCIP_Real *nincreases, SCIP_Real *ndecreases, SCIP_Real increaseweight, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval) |
static SCIP_RETCODE | selectEssentialRounding (SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval) |
static void | addFracCounter (int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval) |
static | SCIP_DECL_HEURCOPY (heurCopyIntshifting) |
static | SCIP_DECL_HEURINIT (heurInitIntshifting) |
static | SCIP_DECL_HEUREXIT (heurExitIntshifting) |
static | SCIP_DECL_HEURINITSOL (heurInitsolIntshifting) |
static | SCIP_DECL_HEUREXEC (heurExecIntshifting) |
SCIP_RETCODE | SCIPincludeHeurIntshifting (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "intshifting" |
Definition at line 45 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and SCIPincludeHeurIntshifting().
◆ HEUR_DESC
#define HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving" |
Definition at line 46 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
Definition at line 47 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -10000 |
Definition at line 48 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_FREQ
#define HEUR_FREQ 10 |
Definition at line 49 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 50 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 51 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 52 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 53 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
◆ MAXSHIFTINGS
#define MAXSHIFTINGS 50 |
maximal number of non improving shiftings
Definition at line 55 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ WEIGHTFACTOR
#define WEIGHTFACTOR 1.1 |
Definition at line 56 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 17 |
Definition at line 57 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEURINIT().
Function Documentation
◆ updateViolations()
|
static |
update row violation arrays after a row's activity value changed
- Parameters
-
scip SCIP data structure row LP row violrows array with currently violated rows violrowpos position of LP rows in violrows array nviolrows pointer to the number of currently violated rows nviolfracrows pointer to the number of violated rows with fractional candidates nfracsinrow array with number of fractional variables for every row oldminactivity old minimal activity value of LP row oldmaxactivity old maximal activity value of LP row newminactivity new minimal activity value of LP row newmaxactivity new maximal activity value of LP row
Definition at line 74 of file heur_intshifting.c.
References NULL, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().
Referenced by updateActivities().
◆ updateActivities()
|
static |
update row activities after a variable's solution value changed
- Parameters
-
scip SCIP data structure minactivities LP row minimal activities maxactivities LP row maximal activities violrows array with currently violated rows violrowpos position of LP rows in violrows array nviolrows pointer to the number of currently violated rows nviolfracrows pointer to the number of violated rows with fractional candidates nfracsinrow array with number of fractional variables for every row nlprows number of rows in current LP var variable that has been changed oldsolval old solution value of variable newsolval new solution value of variable
Definition at line 196 of file heur_intshifting.c.
References NULL, r, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetLPPos(), SCIProwIsInLP(), SCIProwIsLocal(), SCIPvarGetCol(), SCIPvarGetType(), and updateViolations().
Referenced by SCIP_DECL_HEUREXEC().
◆ selectShifting()
|
static |
returns an integer variable, that pushes activity of the row in the given direction with minimal negative impact on other rows; if variables have equal impact, chooses the one with best objective value improvement in corresponding direction; prefer fractional integers over other variables in order to become integral during the process; shifting in a direction is forbidden, if this forces the objective value over the upper bound, or if the variable was already shifted in the opposite direction
- Parameters
-
scip SCIP data structure sol primal solution row LP row rowactivity activity of LP row direction should the activity be increased (+1) or decreased (-1)? nincreases array with weighted number of increasings per variables ndecreases array with weighted number of decreasings per variables increaseweight current weight of increase/decrease updates shiftvar pointer to store the shifting variable, returns NULL if impossible oldsolval pointer to store old solution value of shifting variable newsolval pointer to store new (shifted) solution value of shifting variable
Definition at line 285 of file heur_intshifting.c.
References MAX, NULL, REALABS, SCIP_Bool, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPcolGetVar(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisHugeValue(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_HEUREXEC().
◆ selectEssentialRounding()
|
static |
returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to fix in the other direction; if variables have equal impact, chooses the one with best objective value improvement in corresponding direction; shifting in a direction is forbidden, if this forces the objective value over the upper bound
- Parameters
-
scip SCIP data structure sol primal solution minobj minimal objective value possible after shifting remaining fractional vars lpcands fractional variables in LP nlpcands number of fractional variables in LP shiftvar pointer to store the shifting variable, returns NULL if impossible oldsolval old (fractional) solution value of shifting variable newsolval new (shifted) solution value of shifting variable
Definition at line 435 of file heur_intshifting.c.
References NULL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasIntegral(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), and SCIPvarGetType().
Referenced by SCIP_DECL_HEUREXEC().
◆ addFracCounter()
|
static |
adds a given value to the fractionality counters of the rows in which the given variable appears
- Parameters
-
nfracsinrow array to store number of fractional variables per row violrows array with currently violated rows violrowpos position of LP rows in violrows array nviolfracrows pointer to store the number of violated rows with fractional variables nviolrows the number of currently violated rows (stays unchanged in this method) nlprows number of rows in LP var variable for which the counting should be updated incval value that should be added to the corresponding array entries
Definition at line 513 of file heur_intshifting.c.
References NULL, r, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIProwGetLPPos(), SCIProwIsLocal(), and SCIPvarGetCol().
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 606 of file heur_intshifting.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurIntshifting().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 621 of file heur_intshifting.c.
References DEFAULT_RANDSEED, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcreateRandom(), SCIPcreateSol(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurSetData(), and TRUE.
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 643 of file heur_intshifting.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeRandom(), SCIPfreeSol(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 665 of file heur_intshifting.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 681 of file heur_intshifting.c.
References addFracCounter(), BMSclearMemoryArray, FALSE, HEUR_NAME, MAXSHIFTINGS, nnodes, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebug, SCIPdebugMsg, SCIPendDive(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetNLPIterations(), SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetVars(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPisGE(), SCIPisInfinity(), SCIPisStopped(), SCIPlinkLPSol(), SCIPprintRow(), SCIPprintSol(), SCIPrandomGetInt(), SCIPretransformObj(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIPsetSolVal(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), selectEssentialRounding(), selectShifting(), TRUE, updateActivities(), and WEIGHTFACTOR.