Scippy

SCIP

Solving Constraint Integer Programs

heur_intshifting.c File Reference

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.

Author
Tobias Achterberg

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   'i'
 
#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

◆ HEUR_DESC

#define HEUR_DESC   "LP rounding heuristic with infeasibility recovering and final LP solving"

Definition at line 45 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'i'

Definition at line 46 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -10000

Definition at line 47 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 48 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 49 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 50 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE

Definition at line 51 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 52 of file heur_intshifting.c.

Referenced by SCIPincludeHeurIntshifting().

◆ MAXSHIFTINGS

#define MAXSHIFTINGS   50

maximal number of non improving shiftings

Definition at line 54 of file heur_intshifting.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ WEIGHTFACTOR

#define WEIGHTFACTOR   1.1

Definition at line 55 of file heur_intshifting.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   17

Definition at line 56 of file heur_intshifting.c.

Referenced by SCIP_DECL_HEURINIT().

Function Documentation

◆ updateViolations()

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

update row violation arrays after a row's activity value changed

Parameters
scipSCIP data structure
rowLP row
violrowsarray with currently violated rows
violrowposposition of LP rows in violrows array
nviolrowspointer to the number of currently violated rows
nviolfracrowspointer to the number of violated rows with fractional candidates
nfracsinrowarray with number of fractional variables for every row
oldminactivityold minimal activity value of LP row
oldmaxactivityold maximal activity value of LP row
newminactivitynew minimal activity value of LP row
newmaxactivitynew maximal activity value of LP row

Definition at line 73 of file heur_intshifting.c.

References NULL, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().

Referenced by updateActivities().

◆ updateActivities()

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

update row activities after a variable's solution value changed

Parameters
scipSCIP data structure
minactivitiesLP row minimal activities
maxactivitiesLP row maximal activities
violrowsarray with currently violated rows
violrowposposition of LP rows in violrows array
nviolrowspointer to the number of currently violated rows
nviolfracrowspointer to the number of violated rows with fractional candidates
nfracsinrowarray with number of fractional variables for every row
nlprowsnumber of rows in current LP
varvariable that has been changed
oldsolvalold solution value of variable
newsolvalnew solution value of variable

Definition at line 172 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 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

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
scipSCIP data structure
solprimal solution
rowLP row
rowactivityactivity of LP row
directionshould the activity be increased (+1) or decreased (-1)?
nincreasesarray with weighted number of increasings per variables
ndecreasesarray with weighted number of decreasings per variables
increaseweightcurrent weight of increase/decrease updates
shiftvarpointer to store the shifting variable, returns NULL if impossible
oldsolvalpointer to store old solution value of shifting variable
newsolvalpointer to store new (shifted) solution value of shifting variable

Definition at line 261 of file heur_intshifting.c.

References MAX, MIN, 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 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

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
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after shifting remaining fractional vars
lpcandsfractional variables in LP
nlpcandsnumber of fractional variables in LP
shiftvarpointer to store the shifting variable, returns NULL if impossible
oldsolvalold (fractional) solution value of shifting variable
newsolvalnew (shifted) solution value of shifting variable

Definition at line 411 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 void addFracCounter ( int *  nfracsinrow,
SCIP_ROW **  violrows,
int *  violrowpos,
int *  nviolfracrows,
int  nviolrows,
int  nlprows,
SCIP_VAR var,
int  incval 
)
static

adds a given value to the fractionality counters of the rows in which the given variable appears

Parameters
nfracsinrowarray to store number of fractional variables per row
violrowsarray with currently violated rows
violrowposposition of LP rows in violrows array
nviolfracrowspointer to store the number of violated rows with fractional variables
nviolrowsthe number of currently violated rows (stays unchanged in this method)
nlprowsnumber of rows in LP
varvariable for which the counting should be updated
incvalvalue that should be added to the corresponding array entries

Definition at line 489 of file heur_intshifting.c.

References NULL, r, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIProwGetLPPos(), SCIProwIsLocal(), and SCIPvarGetCol().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyIntshifting  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 582 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurIntshifting().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitIntshifting  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 597 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 SCIP_DECL_HEUREXIT ( heurExitIntshifting  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 619 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeRandom(), SCIPfreeSol(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolIntshifting  )
static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 641 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecIntshifting  )
static

execution method of primal heuristic

Definition at line 657 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_LONGINT_FORMAT, 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.