LP rounding heuristic that tries to recover from intermediate infeasibilities.
Definition in file heur_rounding.c.
#include "blockmemshell/memory.h"
#include "scip/heur_rounding.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.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_sol.h"
#include "scip/scip_solvingstats.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "rounding" |
#define | HEUR_DESC "LP rounding heuristic with infeasibility recovering" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
#define | HEUR_PRIORITY -1000 |
#define | HEUR_FREQ 1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
#define | HEUR_USESSUBSCIP FALSE |
#define | DEFAULT_SUCCESSFACTOR 100 |
#define | DEFAULT_ONCEPERNODE FALSE |
Variables | |
heurdata = SCIPheurGetData(heur) | |
return | SCIP_OKAY |
heurdata | lastlp = -1 |
static SCIP_SOL * | sol |
SCIP_VAR ** | lpcands |
SCIP_Real * | lpcandssol |
SCIP_ROW ** | lprows |
SCIP_Real * | activities |
SCIP_ROW ** | violrows |
int * | violrowpos |
SCIP_Real | obj |
SCIP_Real | bestroundval |
SCIP_Real | minobj = SCIPgetSolTransObj(scip, sol) |
int | nlpcands |
int | nlprows |
int | nfrac |
int | nviolrows |
int | c |
int | r |
SCIP_Longint | nlps |
SCIP_Longint | ncalls |
SCIP_Longint | nsolsfound |
SCIP_Longint | nnodes |
* | result = SCIP_DIDNOTRUN |
#define HEUR_NAME "rounding" |
Definition at line 50 of file heur_rounding.c.
#define HEUR_DESC "LP rounding heuristic with infeasibility recovering" |
Definition at line 51 of file heur_rounding.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING |
Definition at line 52 of file heur_rounding.c.
#define HEUR_PRIORITY -1000 |
Definition at line 53 of file heur_rounding.c.
#define HEUR_FREQ 1 |
Definition at line 54 of file heur_rounding.c.
#define HEUR_FREQOFS 0 |
Definition at line 55 of file heur_rounding.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 56 of file heur_rounding.c.
#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP |
Definition at line 57 of file heur_rounding.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 58 of file heur_rounding.c.
#define DEFAULT_SUCCESSFACTOR 100 |
number of calls per found solution that are considered as standard success, a higher factor causes the heuristic to be called more often
Definition at line 60 of file heur_rounding.c.
Referenced by SCIPincludeHeurRounding().
#define DEFAULT_ONCEPERNODE FALSE |
should the heuristic only be called once per node?
Definition at line 63 of file heur_rounding.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 |
oldactivity | old activity value of LP row |
newactivity | new activity value of LP row |
Definition at line 83 of file heur_rounding.c.
References assert(), NULL, nviolrows, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), 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 |
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 141 of file heur_rounding.c.
References activities, assert(), nlprows, NULL, 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; rounding 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 rounding remaining fractional vars |
row | LP row |
direction | should the activity be increased (+1) or decreased (-1)? |
roundvar | pointer to store the rounding variable, returns NULL if impossible |
oldsolval | pointer to store old (fractional) solution value of rounding variable |
newsolval | pointer to store new (rounded) solution value of rounding variable |
Definition at line 212 of file heur_rounding.c.
References assert(), c, minobj, NULL, obj, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPcolGetVar(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasIntegral(), SCIProwGetCols(), SCIProwGetNLPNonz(), SCIProwGetVals(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetType(), sol, and var.
Referenced by selectDecreaseRounding(), and selectIncreaseRounding().
|
static |
returns a variable, that increases the activity of the row
scip | SCIP data structure |
sol | primal solution |
minobj | minimal objective value possible after rounding remaining fractional vars |
row | LP row |
roundvar | pointer to store the rounding variable, returns NULL if impossible |
oldsolval | old (fractional) solution value of rounding variable |
newsolval | new (rounded) solution value of rounding variable |
Definition at line 314 of file heur_rounding.c.
References minobj, SCIP_Real, selectRounding(), and sol.
Referenced by while().
|
static |
returns a variable, that decreases the activity of the row
scip | SCIP data structure |
sol | primal solution |
minobj | minimal objective value possible after rounding remaining fractional vars |
row | LP row |
roundvar | pointer to store the rounding variable, returns NULL if impossible |
oldsolval | old (fractional) solution value of rounding variable |
newsolval | new (rounded) solution value of rounding variable |
Definition at line 329 of file heur_rounding.c.
References minobj, SCIP_Real, selectRounding(), and sol.
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; rounding 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 rounding remaining fractional vars |
lpcands | fractional variables in LP |
nlpcands | number of fractional variables in LP |
roundvar | pointer to store the rounding variable, returns NULL if impossible |
oldsolval | old (fractional) solution value of rounding variable |
newsolval | new (rounded) solution value of rounding variable |
Definition at line 348 of file heur_rounding.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 |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 431 of file heur_rounding.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRounding().
static assert | ( | heur ! | = NULL | ) |
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.
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 498 of file heur_rounding.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_HEURTIMING_AFTERLPNODE, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 517 of file heur_rounding.c.
References HEUR_TIMING, SCIP_OKAY, and SCIPheurSetTimingmask().
assert | ( | SCIPhasCurrentNodeLP(scip) | ) |
if | ( | SCIPgetLPSolstat(scip) ! | = SCIP_LPSOLSTAT_OPTIMAL | ) |
Definition at line 560 of file heur_rounding.c.
References activities, heurdata, lpcands, lpcandssol, lprows, ncalls, nfrac, nlpcands, nlprows, nlps, nnodes, nsolsfound, NULL, nviolrows, r, result, SCIP_DIDNOTFIND, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, violrowpos, and violrows.
assert | ( | ) |
References minobj.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEURINITSOL(), SCIPincludeHeurRounding(), selectEssentialRounding(), selectRounding(), updateActivities(), updateViolations(), and while().
for | ( | ) |
Definition at line 640 of file heur_rounding.c.
References bestroundval, c, lpcands, lpcandssol, minobj, nlpcands, obj, SCIPfeasCeil(), SCIPfeasFloor(), and SCIPvarGetObj().
while | ( | nfrac | , |
0 | ) |
Definition at line 648 of file heur_rounding.c.
References activities, assert(), lpcands, minobj, nfrac, nlpcands, nlprows, NULL, nviolrows, obj, SCIP_CALL, SCIP_Real, SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetSolOrigObj(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisLE(), SCIPretransformObj(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPvarGetName(), SCIPvarGetObj(), selectDecreaseRounding(), selectEssentialRounding(), selectIncreaseRounding(), sol, updateActivities(), violrowpos, and violrows.
Definition at line 725 of file heur_rounding.c.
References FALSE, nfrac, NULL, nviolrows, result, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIPdebugMsg, SCIPprintSol(), SCIPtrySol(), sol, and TRUE.
SCIPfreeBufferArray | ( | scip | , |
& | violrowpos ) |
References activities, SCIP_OKAY, violrowpos, and violrows.
heurdata = SCIPheurGetData(heur) |
Definition at line 454 of file heur_rounding.c.
return SCIP_OKAY |
Definition at line 459 of file heur_rounding.c.
heurdata lastlp = -1 |
Definition at line 475 of file heur_rounding.c.
sol |
execution method of primal heuristic
Definition at line 531 of file heur_rounding.c.
SCIP_VAR** lpcands |
Definition at line 532 of file heur_rounding.c.
SCIP_Real* lpcandssol |
Definition at line 533 of file heur_rounding.c.
SCIP_ROW** lprows |
Definition at line 534 of file heur_rounding.c.
SCIP_Real* activities |
Definition at line 535 of file heur_rounding.c.
Referenced by calcShiftVal(), determineBound(), if(), optimize(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIPfreeBufferArray(), SCIPfreeBufferArray(), shiftValues(), updateActivities(), updateActivities(), updateRowActivities(), updateSlacks(), while(), and while().
SCIP_ROW** violrows |
Definition at line 536 of file heur_rounding.c.
int* violrowpos |
Definition at line 537 of file heur_rounding.c.
SCIP_Real obj |
Definition at line 538 of file heur_rounding.c.
SCIP_Real bestroundval |
Definition at line 539 of file heur_rounding.c.
Referenced by for().
minobj = SCIPgetSolTransObj(scip, sol) |
Definition at line 540 of file heur_rounding.c.
int nlpcands |
Definition at line 541 of file heur_rounding.c.
int nlprows |
Definition at line 542 of file heur_rounding.c.
int nfrac |
Definition at line 543 of file heur_rounding.c.
int nviolrows |
Definition at line 544 of file heur_rounding.c.
int c |
Definition at line 545 of file heur_rounding.c.
int r |
Definition at line 546 of file heur_rounding.c.
SCIP_Longint nlps |
Definition at line 547 of file heur_rounding.c.
SCIP_Longint ncalls |
Definition at line 548 of file heur_rounding.c.
SCIP_Longint nsolsfound |
Definition at line 549 of file heur_rounding.c.
SCIP_Longint nnodes |
Definition at line 550 of file heur_rounding.c.
* result = SCIP_DIDNOTRUN |
Definition at line 557 of file heur_rounding.c.