SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches

Detailed Description

LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous variables.

Author
Tobias Achterberg

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
 

Functions

static void updateViolations (SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldactivity, SCIP_Real newactivity)
 
static SCIP_RETCODE updateActivities (SCIP *scip, SCIP_Real *activities, 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 (heurCopyShifting)
 
static assert (strcmp(SCIPheurGetName(heur), HEUR_NAME)==0)
 
 assert (SCIPheurGetData(heur)==NULL)
 
 SCIPallocBlockMemory (scip, &heurdata))
 
 SCIPcreateSol (scip, &heurdata->sol, heur))
 
 SCIPcreateRandom (scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
 
 SCIPheurSetData (heur, heurdata)
 
 assert (heurdata !=NULL)
 
 SCIPfreeSol (scip, &heurdata->sol))
 
 SCIPfreeRandom (scip, &heurdata->randnumgen)
 
 SCIPfreeBlockMemory (scip, &heurdata)
 
 SCIPheurSetData (heur, NULL)
 
static SCIP_DECL_HEURINITSOL (heurInitsolShifting)
 
 assert (scip !=NULL)
 
 assert (result !=NULL)
 
 assert (SCIPhasCurrentNodeLP(scip))
 
 if (SCIPgetLPSolstat(scip) !=SCIP_LPSOLSTAT_OPTIMAL)
 
 for (c=0;c< nlpcands;++c) addFracCounter(nfracsinrow
 
 assert (sol !=NULL)
 
 SCIPlinkLPSol (scip, sol))
 
 assert (minobj< SCIPgetCutoffbound(scip))
 
 while ((nfrac > 0||nviolrows > 0) &&nnonimprovingshifts< MAXSHIFTINGS)
 
 if (nfrac==0 &&nviolrows==0)
 
 SCIPfreeBufferArray (scip, &ndecreases)
 
SCIP_RETCODE SCIPincludeHeurShifting (SCIP *scip)
 

Variables

heurdata lastlp = -1
 
return SCIP_OKAY
 
 heurdata = SCIPheurGetData(heur)
 
static SCIP_SOLsol
 
SCIP_VAR ** lpcands
 
SCIP_Reallpcandssol
 
SCIP_ROW ** lprows
 
SCIP_Realactivities
 
SCIP_ROW ** violrows
 
SCIP_Realnincreases
 
SCIP_Realndecreases
 
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
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "shifting"

Definition at line 52 of file heur_shifting.c.

◆ HEUR_DESC

#define HEUR_DESC   "LP rounding heuristic with infeasibility recovering also using continuous variables"

Definition at line 53 of file heur_shifting.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 54 of file heur_shifting.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -5000

Definition at line 55 of file heur_shifting.c.

◆ HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 56 of file heur_shifting.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 57 of file heur_shifting.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 58 of file heur_shifting.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 59 of file heur_shifting.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 60 of file heur_shifting.c.

◆ MAXSHIFTINGS

#define MAXSHIFTINGS   50

maximal number of non improving shiftings

Definition at line 62 of file heur_shifting.c.

◆ WEIGHTFACTOR

#define WEIGHTFACTOR   1.1

Definition at line 63 of file heur_shifting.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   31

initial random seed

Definition at line 64 of file heur_shifting.c.

Function Documentation

◆ updateViolations()

static void updateViolations ( SCIP * scip,
SCIP_ROW * row,
SCIP_ROW ** violrows,
int * violrowpos,
int * nviolrows,
int * nviolfracrows,
int * nfracsinrow,
SCIP_Real oldactivity,
SCIP_Real newactivity )
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
oldactivityold activity value of LP row
newactivitynew 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().

◆ updateActivities()

static SCIP_RETCODE updateActivities ( SCIP * scip,
SCIP_Real * activities,
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
activitiesLP row 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 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().

◆ 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 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

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 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().

◆ 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 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().

◆ 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 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().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyShifting )
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() [1/8]

static 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() [2/8]

assert ( SCIPheurGetData(heur) = =NULL)

References NULL.

◆ SCIPallocBlockMemory()

SCIPallocBlockMemory ( scip ,
& heurdata )

References heurdata.

◆ SCIPcreateSol()

SCIPcreateSol ( scip ,
&heurdata-> sol,
heur  )

References heurdata.

◆ SCIPcreateRandom()

SCIPcreateRandom ( scip ,
&heurdata-> randnumgen,
DEFAULT_RANDSEED ,
TRUE  )

References DEFAULT_RANDSEED, heurdata, and TRUE.

◆ SCIPheurSetData() [1/2]

SCIPheurSetData ( heur ,
heurdata  )

References heurdata.

◆ assert() [3/8]

assert ( heurdata ! = NULL)

References heurdata, and NULL.

◆ SCIPfreeSol()

SCIPfreeSol ( scip ,
&heurdata-> sol )

References heurdata.

◆ SCIPfreeRandom()

SCIPfreeRandom ( scip ,
&heurdata-> randnumgen )

References heurdata.

◆ SCIPfreeBlockMemory()

SCIPfreeBlockMemory ( scip ,
& heurdata )

References heurdata.

◆ SCIPheurSetData() [2/2]

SCIPheurSetData ( heur ,
NULL  )

References NULL, and SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolShifting )
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() [4/8]

assert ( scip ! = NULL)

References NULL.

◆ assert() [5/8]

assert ( result ! = NULL)

References NULL, and result.

◆ assert() [6/8]

assert ( SCIPhasCurrentNodeLP(scip) )

◆ if() [1/2]

◆ for()

for ( )

◆ assert() [7/8]

assert ( sol ! = NULL)

References NULL, and sol.

◆ SCIPlinkLPSol()

SCIPlinkLPSol ( scip ,
sol  )

References minobj, and sol.

◆ assert() [8/8]

◆ while()

◆ if() [2/2]

if ( nfrac = = 0 && nviolrows == 0)

◆ SCIPfreeBufferArray()

SCIPfreeBufferArray ( scip ,
& ndecreases )

Variable Documentation

◆ lastlp

heurdata lastlp = -1

Definition at line 620 of file heur_shifting.c.

◆ SCIP_OKAY

return SCIP_OKAY

Definition at line 628 of file heur_shifting.c.

◆ heurdata

heurdata = SCIPheurGetData(heur)

Definition at line 640 of file heur_shifting.c.

◆ sol

sol
Initial value:
{
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77

execution method of primal heuristic

Definition at line 674 of file heur_shifting.c.

◆ lpcands

lpcands[c]

Definition at line 675 of file heur_shifting.c.

◆ lpcandssol

SCIP_Real* lpcandssol

Definition at line 676 of file heur_shifting.c.

◆ lprows

SCIP_ROW** lprows

Definition at line 677 of file heur_shifting.c.

◆ activities

SCIP_Real* activities

Definition at line 678 of file heur_shifting.c.

◆ violrows

violrows

Definition at line 679 of file heur_shifting.c.

◆ nincreases

SCIP_Real* nincreases

Definition at line 680 of file heur_shifting.c.

◆ ndecreases

SCIP_Real* ndecreases

Definition at line 681 of file heur_shifting.c.

◆ violrowpos

violrowpos

Definition at line 682 of file heur_shifting.c.

◆ nfracsinrow

int* nfracsinrow

Definition at line 683 of file heur_shifting.c.

◆ increaseweight

increaseweight = 1.0

Definition at line 684 of file heur_shifting.c.

◆ obj

SCIP_Real obj

Definition at line 685 of file heur_shifting.c.

◆ bestshiftval

SCIP_Real bestshiftval

Definition at line 686 of file heur_shifting.c.

◆ minobj

minobj = SCIPgetSolTransObj(scip, sol)

Definition at line 687 of file heur_shifting.c.

◆ nlpcands

int nlpcands

Definition at line 688 of file heur_shifting.c.

◆ nlprows

nlprows

Definition at line 689 of file heur_shifting.c.

◆ nvars

int nvars

Definition at line 690 of file heur_shifting.c.

◆ nfrac

int nfrac

Definition at line 691 of file heur_shifting.c.

◆ nviolrows

nviolrows

Definition at line 692 of file heur_shifting.c.

◆ nviolfracrows

& nviolfracrows = 0

Definition at line 693 of file heur_shifting.c.

◆ nprevviolrows

int nprevviolrows

Definition at line 694 of file heur_shifting.c.

◆ minnviolrows

minnviolrows = INT_MAX

Definition at line 695 of file heur_shifting.c.

◆ nnonimprovingshifts

nnonimprovingshifts = 0

Definition at line 696 of file heur_shifting.c.

◆ c

int c

Definition at line 697 of file heur_shifting.c.

◆ r

int r

Definition at line 698 of file heur_shifting.c.

◆ nlps

Definition at line 699 of file heur_shifting.c.

◆ ncalls

SCIP_Longint ncalls

Definition at line 700 of file heur_shifting.c.

◆ nsolsfound

SCIP_Longint nsolsfound

Definition at line 701 of file heur_shifting.c.

◆ nnodes

SCIP_Longint nnodes

Definition at line 702 of file heur_shifting.c.

◆ result

* result = SCIP_DIDNOTRUN

Definition at line 709 of file heur_shifting.c.