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

Detailed Description

zirounding primal heuristic

Author
Gregor Hendel

Definition in file heur_zirounding.c.

#include "blockmemshell/memory.h"
#include "scip/heur_zirounding.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   "zirounding"
 
#define HEUR_DESC   "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING
 
#define HEUR_PRIORITY   -500
 
#define HEUR_FREQ   1
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE
 
#define HEUR_USESSUBSCIP   FALSE
 
#define DEFAULT_MAXROUNDINGLOOPS   2
 
#define DEFAULT_STOPZIROUND   TRUE
 
#define DEFAULT_STOPPERCENTAGE   0.02
 
#define DEFAULT_MINSTOPNCALLS   1000
 
#define MINSHIFT   1e-4
 

Functions

static SCIP_Real getZiValue (SCIP *scip, SCIP_Real val)
 
static void calculateBounds (SCIP *scip, SCIP_VAR *var, SCIP_Real currentvalue, SCIP_Real *upperbound, SCIP_Real *lowerbound, SCIP_Real *upslacks, SCIP_Real *downslacks, int nslacks, SCIP_Bool *numericalerror)
 
static SCIP_RETCODE updateSlacks (SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real shiftvalue, SCIP_Real *upslacks, SCIP_Real *downslacks, SCIP_Real *activities, SCIP_VAR **slackvars, SCIP_Real *slackcoeffs, int nslacks)
 
static void rowFindSlackVar (SCIP *scip, SCIP_ROW *row, SCIP_VAR **varpointer, SCIP_Real *coeffpointer)
 
static SCIP_DECL_HEURCOPY (heurCopyZirounding)
 
static SCIP_DECL_HEURFREE (heurFreeZirounding)
 
static SCIP_DECL_HEURINIT (heurInitZirounding)
 
static assert (strcmp(SCIPheurGetName(heur), HEUR_NAME)==0)
 
 assert (heurdata !=NULL)
 
 SCIPfreeSol (scip, &heurdata->sol))
 
static SCIP_DECL_HEURINITSOL (heurInitsolZirounding)
 
static SCIP_DECL_HEUREXEC (heurExecZirounding)
 
SCIP_RETCODE SCIPincludeHeurZirounding (SCIP *scip)
 

Variables

 heurdata = SCIPheurGetData(heur)
 
return SCIP_OKAY
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "zirounding"

Definition at line 50 of file heur_zirounding.c.

◆ HEUR_DESC

#define HEUR_DESC   "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"

Definition at line 51 of file heur_zirounding.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 52 of file heur_zirounding.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -500

Definition at line 53 of file heur_zirounding.c.

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 54 of file heur_zirounding.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 55 of file heur_zirounding.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 56 of file heur_zirounding.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 57 of file heur_zirounding.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 58 of file heur_zirounding.c.

◆ DEFAULT_MAXROUNDINGLOOPS

#define DEFAULT_MAXROUNDINGLOOPS   2

delimits the number of main loops, can be set to -1 for no limit

Definition at line 60 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_STOPZIROUND

#define DEFAULT_STOPZIROUND   TRUE

deactivation check is enabled by default

Definition at line 61 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_STOPPERCENTAGE

#define DEFAULT_STOPPERCENTAGE   0.02

the tolerance percentage after which zirounding will not be executed anymore

Definition at line 62 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_MINSTOPNCALLS

#define DEFAULT_MINSTOPNCALLS   1000

number of heuristic calls before deactivation check

Definition at line 63 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ MINSHIFT

#define MINSHIFT   1e-4

minimum shift value for every single step

Definition at line 65 of file heur_zirounding.c.

Referenced by calculateBounds(), and SCIP_DECL_HEUREXEC().

Enumeration Type Documentation

◆ Direction

enum Direction
Enumerator
DIRECTION_UP 
DIRECTION_DOWN 

Definition at line 82 of file heur_zirounding.c.

Function Documentation

◆ getZiValue()

static SCIP_Real getZiValue ( SCIP * scip,
SCIP_Real val )
static

returns the fractionality of a value x, which is calculated as zivalue(x) = min(x-floor(x), ceil(x)-x)

Parameters
scippointer to current SCIP data structure
valthe value for which the fractionality should be computed

Definition at line 95 of file heur_zirounding.c.

References assert(), MIN, NULL, SCIP_Real, SCIPfeasCeil(), and SCIPfeasFloor().

Referenced by SCIP_DECL_HEUREXEC().

◆ calculateBounds()

static void calculateBounds ( SCIP * scip,
SCIP_VAR * var,
SCIP_Real currentvalue,
SCIP_Real * upperbound,
SCIP_Real * lowerbound,
SCIP_Real * upslacks,
SCIP_Real * downslacks,
int nslacks,
SCIP_Bool * numericalerror )
static

determines shifting bounds for variable

Parameters
scippointer to current SCIP data structure
varthe variable for which lb and ub have to be calculated
currentvaluethe current value of var in the working solution
upperboundpointer to store the calculated upper bound on the variable shift
lowerboundpointer to store the calculated lower bound on the variable shift
upslacksarray that contains the slacks between row activities and the right hand sides of the rows
downslacksarray that contains lhs slacks
nslackscurrent number of slacks
numericalerrorflag to determine whether a numerical error occurred

Definition at line 113 of file heur_zirounding.c.

References assert(), i, MAX, MIN, MINSHIFT, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPinfinity(), SCIPisFeasLT(), SCIPisInfinity(), SCIProwGetLPPos(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and var.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateSlacks()

static SCIP_RETCODE updateSlacks ( SCIP * scip,
SCIP_SOL * sol,
SCIP_VAR * var,
SCIP_Real shiftvalue,
SCIP_Real * upslacks,
SCIP_Real * downslacks,
SCIP_Real * activities,
SCIP_VAR ** slackvars,
SCIP_Real * slackcoeffs,
int nslacks )
static

when a variable is shifted, the activities and slacks of all rows it appears in have to be updated

Parameters
scippointer to current SCIP data structure
solworking solution
varpointer to variable to be modified
shiftvaluethe value by which the variable is shifted
upslacksupslacks of all rows the variable appears in
downslacksdownslacks of all rows the variable appears in
activitiesactivities of the LP rows
slackvarsthe slack variables for equality rows
slackcoeffsthe slack variable coefficients
nslackssize of the arrays

Definition at line 237 of file heur_zirounding.c.

References activities, assert(), i, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), sol, and var.

Referenced by SCIP_DECL_HEUREXEC().

◆ rowFindSlackVar()

static void rowFindSlackVar ( SCIP * scip,
SCIP_ROW * row,
SCIP_VAR ** varpointer,
SCIP_Real * coeffpointer )
static

finds a continuous slack variable for an equation row, NULL if none exists

Parameters
scippointer to current SCIP data structure
rowthe row for which a slack variable is searched
varpointerpointer to store the slack variable
coeffpointerpointer to store the coefficient of the slack variable

Definition at line 328 of file heur_zirounding.c.

References assert(), NULL, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetVar(), SCIPdebugMsg, SCIPisFeasEQ(), SCIProwGetCols(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyZirounding )
static

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

Definition at line 387 of file heur_zirounding.c.

References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurZirounding().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeZirounding )
static

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

Definition at line 401 of file heur_zirounding.c.

References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitZirounding )
static

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

Definition at line 419 of file heur_zirounding.c.

References assert(), HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPheurGetData(), and SCIPheurGetName().

◆ assert() [1/2]

static assert ( strcmp(SCIPheurGetName(heur), HEUR_NAME) = =0)

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

References HEUR_NAME.

◆ assert() [2/2]

assert ( heurdata ! = NULL)

References heurdata, and NULL.

◆ SCIPfreeSol()

SCIPfreeSol ( scip ,
&heurdata-> sol )

References heurdata.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolZirounding )
static

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

Definition at line 453 of file heur_zirounding.c.

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecZirounding )
static

execution method of primal heuristic

Definition at line 470 of file heur_zirounding.c.

References activities, assert(), BMSclearMemoryArray, BMScopyMemoryArray, c, calculateBounds(), DIRECTION_DOWN, DIRECTION_UP, FALSE, getZiValue(), HEUR_NAME, heurdata, i, lpcands, lpcandssol, MAX, MIN, MINSHIFT, nlpcands, nlps, NULL, r, result, rowFindSlackVar(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArrayNull, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNLPRows(), SCIPgetNLPs(), SCIPgetRowActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisGE(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIPlinkLPSol(), SCIPprintSol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetCol(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), sol, TRUE, updateSlacks(), and var.

Variable Documentation

◆ heurdata

heurdata = SCIPheurGetData(heur)

Definition at line 442 of file heur_zirounding.c.

◆ SCIP_OKAY

return SCIP_OKAY

Definition at line 448 of file heur_zirounding.c.