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

Detailed Description

LP rounding heuristic that tries to recover from intermediate infeasibilities.

Author
Tobias Achterberg

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
 

Functions

static void updateViolations (SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, SCIP_Real oldactivity, SCIP_Real newactivity)
 
static SCIP_RETCODE updateActivities (SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
 
static SCIP_RETCODE selectRounding (SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, int direction, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
 
static SCIP_RETCODE selectIncreaseRounding (SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
 
static SCIP_RETCODE selectDecreaseRounding (SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, 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 **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
 
static SCIP_DECL_HEURCOPY (heurCopyRounding)
 
static assert (heur !=NULL)
 
 assert (strcmp(SCIPheurGetName(heur), HEUR_NAME)==0)
 
 assert (scip !=NULL)
 
 assert (heurdata !=NULL)
 
 SCIPfreeBlockMemory (scip, &heurdata)
 
 SCIPheurSetData (heur, NULL)
 
 SCIPcreateSol (scip, &heurdata->sol, heur))
 
 SCIPfreeSol (scip, &heurdata->sol))
 
static SCIP_DECL_HEURINITSOL (heurInitsolRounding)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolRounding)
 
 assert (result !=NULL)
 
 assert (SCIPhasCurrentNodeLP(scip))
 
 if (SCIPgetLPSolstat(scip) !=SCIP_LPSOLSTAT_OPTIMAL)
 
 assert (sol !=NULL)
 
 SCIPlinkLPSol (scip, sol))
 
 assert (minobj< SCIPgetCutoffbound(scip))
 
 for (c=0;c< nlpcands;++c)
 
 while (nfrac > 0)
 
 if (nfrac==0 &&nviolrows==0)
 
 SCIPfreeBufferArray (scip, &violrowpos)
 
SCIP_RETCODE SCIPincludeHeurRounding (SCIP *scip)
 

Variables

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

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "rounding"

Definition at line 50 of file heur_rounding.c.

◆ HEUR_DESC

#define HEUR_DESC   "LP rounding heuristic with infeasibility recovering"

Definition at line 51 of file heur_rounding.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 52 of file heur_rounding.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1000

Definition at line 53 of file heur_rounding.c.

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 54 of file heur_rounding.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 55 of file heur_rounding.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 56 of file heur_rounding.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 57 of file heur_rounding.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 58 of file heur_rounding.c.

◆ DEFAULT_SUCCESSFACTOR

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

◆ DEFAULT_ONCEPERNODE

#define DEFAULT_ONCEPERNODE   FALSE

should the heuristic only be called once per node?

Definition at line 63 of file heur_rounding.c.

Function Documentation

◆ updateViolations()

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

◆ updateActivities()

static SCIP_RETCODE updateActivities ( SCIP * scip,
SCIP_Real * activities,
SCIP_ROW ** violrows,
int * violrowpos,
int * nviolrows,
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
nlprowsnumber of rows in current LP
varvariable that has been changed
oldsolvalold solution value of variable
newsolvalnew 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().

◆ selectRounding()

static SCIP_RETCODE selectRounding ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real minobj,
SCIP_ROW * row,
int direction,
SCIP_VAR ** roundvar,
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; rounding 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 rounding remaining fractional vars
rowLP row
directionshould the activity be increased (+1) or decreased (-1)?
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalpointer to store old (fractional) solution value of rounding variable
newsolvalpointer 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().

◆ selectIncreaseRounding()

static SCIP_RETCODE selectIncreaseRounding ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real minobj,
SCIP_ROW * row,
SCIP_VAR ** roundvar,
SCIP_Real * oldsolval,
SCIP_Real * newsolval )
static

returns a variable, that increases the activity of the row

Parameters
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after rounding remaining fractional vars
rowLP row
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalold (fractional) solution value of rounding variable
newsolvalnew (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().

◆ selectDecreaseRounding()

static SCIP_RETCODE selectDecreaseRounding ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real minobj,
SCIP_ROW * row,
SCIP_VAR ** roundvar,
SCIP_Real * oldsolval,
SCIP_Real * newsolval )
static

returns a variable, that decreases the activity of the row

Parameters
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after rounding remaining fractional vars
rowLP row
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalold (fractional) solution value of rounding variable
newsolvalnew (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().

◆ selectEssentialRounding()

static SCIP_RETCODE selectEssentialRounding ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real minobj,
SCIP_VAR ** lpcands,
int nlpcands,
SCIP_VAR ** roundvar,
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; rounding 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 rounding remaining fractional vars
lpcandsfractional variables in LP
nlpcandsnumber of fractional variables in LP
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalold (fractional) solution value of rounding variable
newsolvalnew (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().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyRounding )
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().

◆ assert() [1/8]

static assert ( heur ! = NULL)

destructor of primal heuristic to free user data (called when SCIP is exiting)

References NULL.

◆ assert() [2/8]

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

assert ( scip ! = NULL)

References NULL.

◆ assert() [4/8]

assert ( heurdata ! = NULL)

References heurdata, and NULL.

◆ SCIPfreeBlockMemory()

SCIPfreeBlockMemory ( scip ,
& heurdata )

References heurdata.

◆ SCIPheurSetData()

SCIPheurSetData ( heur ,
NULL  )

References NULL.

◆ SCIPcreateSol()

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

References heurdata.

◆ SCIPfreeSol()

SCIPfreeSol ( scip ,
&heurdata-> sol )

References heurdata, and SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolRounding )
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().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolRounding )
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() [5/8]

assert ( result ! = NULL)

References NULL, and result.

◆ assert() [6/8]

assert ( SCIPhasCurrentNodeLP(scip) )

◆ if() [1/2]

◆ assert() [7/8]

assert ( sol ! = NULL)

References NULL, and sol.

◆ SCIPlinkLPSol()

SCIPlinkLPSol ( scip ,
sol  )

References minobj, and sol.

◆ assert() [8/8]

◆ for()

for ( )

◆ while()

◆ if() [2/2]

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

◆ SCIPfreeBufferArray()

SCIPfreeBufferArray ( scip ,
& violrowpos )

Variable Documentation

◆ heurdata

heurdata = SCIPheurGetData(heur)

Definition at line 454 of file heur_rounding.c.

◆ SCIP_OKAY

return SCIP_OKAY

Definition at line 459 of file heur_rounding.c.

◆ lastlp

heurdata lastlp = -1

Definition at line 475 of file heur_rounding.c.

◆ sol

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

execution method of primal heuristic

Definition at line 531 of file heur_rounding.c.

◆ lpcands

SCIP_VAR** lpcands

Definition at line 532 of file heur_rounding.c.

◆ lpcandssol

SCIP_Real* lpcandssol

Definition at line 533 of file heur_rounding.c.

◆ lprows

SCIP_ROW** lprows

Definition at line 534 of file heur_rounding.c.

◆ activities

◆ violrows

SCIP_ROW** violrows

Definition at line 536 of file heur_rounding.c.

◆ violrowpos

int* violrowpos

Definition at line 537 of file heur_rounding.c.

◆ obj

SCIP_Real obj

Definition at line 538 of file heur_rounding.c.

◆ bestroundval

SCIP_Real bestroundval

Definition at line 539 of file heur_rounding.c.

Referenced by for().

◆ minobj

minobj = SCIPgetSolTransObj(scip, sol)

Definition at line 540 of file heur_rounding.c.

◆ nlpcands

int nlpcands

Definition at line 541 of file heur_rounding.c.

◆ nlprows

int nlprows

Definition at line 542 of file heur_rounding.c.

◆ nfrac

int nfrac

Definition at line 543 of file heur_rounding.c.

◆ nviolrows

int nviolrows

Definition at line 544 of file heur_rounding.c.

◆ c

int c

Definition at line 545 of file heur_rounding.c.

◆ r

int r

Definition at line 546 of file heur_rounding.c.

◆ nlps

Definition at line 547 of file heur_rounding.c.

◆ ncalls

SCIP_Longint ncalls

Definition at line 548 of file heur_rounding.c.

◆ nsolsfound

SCIP_Longint nsolsfound

Definition at line 549 of file heur_rounding.c.

◆ nnodes

SCIP_Longint nnodes

Definition at line 550 of file heur_rounding.c.

◆ result

* result = SCIP_DIDNOTRUN

Definition at line 557 of file heur_rounding.c.