LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous variables.
Definition in file heur_shifting.c.
#include "blockmemshell/memory.h"
#include "scip/heur_shifting.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_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 "shifting" |
#define | HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
#define | HEUR_PRIORITY -5000 |
#define | HEUR_FREQ 10 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
#define | HEUR_USESSUBSCIP FALSE |
#define | MAXSHIFTINGS 50 |
#define | WEIGHTFACTOR 1.1 |
#define | DEFAULT_RANDSEED 31 |
Variables | |
heurdata | lastlp = -1 |
return | SCIP_OKAY |
heurdata = SCIPheurGetData(heur) | |
static SCIP_SOL * | sol |
SCIP_VAR ** | lpcands |
SCIP_Real * | lpcandssol |
SCIP_ROW ** | lprows |
SCIP_Real * | activities |
SCIP_ROW ** | violrows |
SCIP_Real * | nincreases |
SCIP_Real * | ndecreases |
int * | violrowpos |
int * | nfracsinrow |
SCIP_Real | increaseweight = 1.0 |
SCIP_Real | obj |
SCIP_Real | bestshiftval |
SCIP_Real | minobj = SCIPgetSolTransObj(scip, sol) |
int | nlpcands |
int | nlprows |
int | nvars |
int | nfrac |
int | nviolrows |
int | nviolfracrows = 0 |
int | nprevviolrows |
int | minnviolrows = INT_MAX |
int | nnonimprovingshifts = 0 |
int | c |
int | r |
SCIP_Longint | nlps |
SCIP_Longint | ncalls |
SCIP_Longint | nsolsfound |
SCIP_Longint | nnodes |
* | result = SCIP_DIDNOTRUN |
#define HEUR_NAME "shifting" |
Definition at line 52 of file heur_shifting.c.
#define HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables" |
Definition at line 53 of file heur_shifting.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
Definition at line 54 of file heur_shifting.c.
#define HEUR_PRIORITY -5000 |
Definition at line 55 of file heur_shifting.c.
#define HEUR_FREQ 10 |
Definition at line 56 of file heur_shifting.c.
#define HEUR_FREQOFS 0 |
Definition at line 57 of file heur_shifting.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 58 of file heur_shifting.c.
#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
Definition at line 59 of file heur_shifting.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 60 of file heur_shifting.c.
#define MAXSHIFTINGS 50 |
maximal number of non improving shiftings
Definition at line 62 of file heur_shifting.c.
#define WEIGHTFACTOR 1.1 |
Definition at line 63 of file heur_shifting.c.
#define DEFAULT_RANDSEED 31 |
initial random seed
Definition at line 64 of file heur_shifting.c.
|
static |
update row violation arrays after a row's activity value changed
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 |
oldactivity | old activity value of LP row |
newactivity | new activity value of LP row |
Definition at line 82 of file heur_shifting.c.
References assert(), nfracsinrow, NULL, nviolfracrows, nviolrows, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), violrowpos, and violrows.
Referenced by updateActivities().
|
static |
update row activities after a variable's solution value changed
scip | SCIP data structure |
activities | LP row 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 200 of file heur_shifting.c.
References activities, assert(), nfracsinrow, nlprows, NULL, nviolfracrows, nviolrows, r, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetLPPos(), SCIProwIsInLP(), SCIProwIsLocal(), SCIPvarGetCol(), updateViolations(), var, violrowpos, and violrows.
Referenced by while().
|
static |
returns a 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
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 275 of file heur_shifting.c.
References assert(), c, increaseweight, MAX, MIN, ndecreases, nincreases, NULL, 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(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), sol, and var.
Referenced by while().
|
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
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 428 of file heur_shifting.c.
References assert(), lpcands, minobj, nlpcands, NULL, obj, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasIntegral(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetType(), sol, and var.
Referenced by while().
|
static |
adds a given value to the fractionality counters of the rows in which the given variable appears
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 506 of file heur_shifting.c.
References assert(), nfracsinrow, nlprows, nviolfracrows, nviolrows, r, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIProwGetLPPos(), SCIProwIsLocal(), SCIPvarGetCol(), var, violrowpos, and violrows.
Referenced by while().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 595 of file heur_shifting.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurShifting().
assert | ( | strcmp(SCIPheurGetName(heur), HEUR_NAME) | = =0 | ) |
initialization method of primal heuristic (called after problem was transformed)
deinitialization method of primal heuristic (called before transformed problem is freed)
References HEUR_NAME.
assert | ( | SCIPheurGetData(heur) | = =NULL | ) |
References NULL.
SCIPallocBlockMemory | ( | scip | , |
& | heurdata ) |
References heurdata.
SCIPcreateRandom | ( | scip | , |
&heurdata-> | randnumgen, | ||
DEFAULT_RANDSEED | , | ||
TRUE | ) |
References DEFAULT_RANDSEED, heurdata, and TRUE.
SCIPfreeBlockMemory | ( | scip | , |
& | heurdata ) |
References heurdata.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 655 of file heur_shifting.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().
assert | ( | SCIPhasCurrentNodeLP(scip) | ) |
if | ( | SCIPgetLPSolstat(scip) ! | = SCIP_LPSOLSTAT_OPTIMAL | ) |
Definition at line 712 of file heur_shifting.c.
References activities, heurdata, lpcands, lpcandssol, lprows, ncalls, ndecreases, nfrac, nfracsinrow, nincreases, nlpcands, nlprows, nlps, nnodes, nsolsfound, NULL, nvars, nviolrows, r, result, SCIP_DIDNOTFIND, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, violrowpos, and violrows.
for | ( | ) |
Definition at line 807 of file heur_shifting.c.
References bestshiftval, c, lpcands, lpcandssol, minobj, nlpcands, obj, SCIPfeasCeil(), SCIPfeasFloor(), and SCIPvarGetObj().
assert | ( | ) |
References minobj.
Referenced by addFracCounter(), SCIP_DECL_HEURCOPY(), SCIP_DECL_HEURINITSOL(), SCIPincludeHeurShifting(), selectEssentialRounding(), selectShifting(), updateActivities(), updateViolations(), and while().
while | ( | ) |
Definition at line 818 of file heur_shifting.c.
References activities, addFracCounter(), assert(), heurdata, i, increaseweight, lpcands, MAXSHIFTINGS, minnviolrows, minobj, ndecreases, nfrac, nfracsinrow, nincreases, nlpcands, nlprows, nnonimprovingshifts, nprevviolrows, NULL, nvars, nviolfracrows, nviolrows, obj, SCIP_Bool, SCIP_CALL, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPdebug, SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetSolOrigObj(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPprintRow(), SCIPrandomGetInt(), SCIPretransformObj(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), selectEssentialRounding(), selectShifting(), sol, updateActivities(), violrowpos, violrows, and WEIGHTFACTOR.
Definition at line 961 of file heur_shifting.c.
References FALSE, nfrac, NULL, nviolrows, result, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIPdebug, SCIPdebugMsg, SCIPprintSol(), SCIPtrySol(), sol, and TRUE.
SCIPfreeBufferArray | ( | scip | , |
& | ndecreases ) |
References activities, ndecreases, nfracsinrow, nincreases, SCIP_OKAY, violrowpos, and violrows.
heurdata lastlp = -1 |
Definition at line 620 of file heur_shifting.c.
return SCIP_OKAY |
Definition at line 628 of file heur_shifting.c.
heurdata = SCIPheurGetData(heur) |
Definition at line 640 of file heur_shifting.c.
sol |
execution method of primal heuristic
Definition at line 674 of file heur_shifting.c.
lpcands[c] |
Definition at line 675 of file heur_shifting.c.
SCIP_Real* lpcandssol |
Definition at line 676 of file heur_shifting.c.
SCIP_ROW** lprows |
Definition at line 677 of file heur_shifting.c.
SCIP_Real* activities |
Definition at line 678 of file heur_shifting.c.
violrows |
Definition at line 679 of file heur_shifting.c.
SCIP_Real* nincreases |
Definition at line 680 of file heur_shifting.c.
SCIP_Real* ndecreases |
Definition at line 681 of file heur_shifting.c.
violrowpos |
Definition at line 682 of file heur_shifting.c.
int* nfracsinrow |
Definition at line 683 of file heur_shifting.c.
increaseweight = 1.0 |
Definition at line 684 of file heur_shifting.c.
SCIP_Real obj |
Definition at line 685 of file heur_shifting.c.
SCIP_Real bestshiftval |
Definition at line 686 of file heur_shifting.c.
minobj = SCIPgetSolTransObj(scip, sol) |
Definition at line 687 of file heur_shifting.c.
int nlpcands |
Definition at line 688 of file heur_shifting.c.
nlprows |
Definition at line 689 of file heur_shifting.c.
int nvars |
Definition at line 690 of file heur_shifting.c.
int nfrac |
Definition at line 691 of file heur_shifting.c.
nviolrows |
Definition at line 692 of file heur_shifting.c.
& nviolfracrows = 0 |
Definition at line 693 of file heur_shifting.c.
int nprevviolrows |
Definition at line 694 of file heur_shifting.c.
minnviolrows = INT_MAX |
Definition at line 695 of file heur_shifting.c.
nnonimprovingshifts = 0 |
Definition at line 696 of file heur_shifting.c.
int c |
Definition at line 697 of file heur_shifting.c.
int r |
Definition at line 698 of file heur_shifting.c.
SCIP_Longint nlps |
Definition at line 699 of file heur_shifting.c.
SCIP_Longint ncalls |
Definition at line 700 of file heur_shifting.c.
SCIP_Longint nsolsfound |
Definition at line 701 of file heur_shifting.c.
SCIP_Longint nnodes |
Definition at line 702 of file heur_shifting.c.
* result = SCIP_DIDNOTRUN |
Definition at line 709 of file heur_shifting.c.