heur_twoopt.c File Reference

Detailed Description

primal heuristic to improve incumbent solution by flipping pairs of variables

Author

Timo Berthold

Gregor Hendel

Definition in file heur_twoopt.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_twoopt.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME   "twoopt"
#define	HEUR_DESC   "primal heuristic to improve incumbent solution by flipping pairs of variables"
#define	HEUR_DISPCHAR   'B'
#define	HEUR_PRIORITY   -20100
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
#define	HEUR_USESSUBSCIP   FALSE
#define	DEFAULT_INTOPT   FALSE
#define	DEFAULT_WAITINGNODES   0
#define	DEFAULT_MATCHINGRATE   0.5
#define	DEFAULT_MAXNSLAVES   199
#define	DEFAULT_ARRAYSIZE   10

Typedefs
typedef enum Opttype	OPTTYPE
typedef enum Direction	DIRECTION

Enumerations
enum	Opttype {   OPTTYPE_BINARY = 1,   OPTTYPE_INTEGER = 2 }
enum	Direction {   DIRECTION_UP = 1,   DIRECTION_DOWN = -1,   DIRECTION_NONE = 0,   DIRECTION_UP = 1,   DIRECTION_DOWN = -1 }

Functions
static SCIP_RETCODE	shiftValues (SCIP *scip, SCIP_VAR *master, SCIP_VAR *slave, SCIP_Real mastersolval, DIRECTION masterdir, SCIP_Real slavesolval, DIRECTION slavedir, SCIP_Real shiftval, SCIP_Real *activities, int nrows, SCIP_Bool *feasible)
static int	varColCompare (SCIP_VAR *var1, SCIP_VAR *var2)
static	SCIP_DECL_SORTPTRCOMP (SCIPvarcolComp)
static SCIP_Bool	checkConstraintMatching (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real matchingrate)
static SCIP_Real	determineBound (SCIP *scip, SCIP_SOL *sol, SCIP_VAR *master, DIRECTION masterdirection, SCIP_VAR *slave, DIRECTION slavedirection, SCIP_Real *activities, int nrows)
static void	disposeVariable (SCIP_VAR **vars, int *blockend, int varindex)
static SCIP_RETCODE	innerPresolve (SCIP *scip, SCIP_VAR **vars, SCIP_VAR ***varspointer, int nvars, int *nblocks, int *maxblocksize, int *nblockvars, int **blockstart, int **blockend, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	presolveTwoOpt (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
static	SCIP_DECL_HEURCOPY (heurCopyTwoopt)
static	SCIP_DECL_HEURFREE (heurFreeTwoopt)
static	SCIP_DECL_HEURINIT (heurInitTwoopt)
static SCIP_RETCODE	optimize (SCIP *scip, SCIP_SOL *worksol, SCIP_VAR **vars, int *blockstart, int *blockend, int nblocks, OPTTYPE opttype, SCIP_Real *activities, int nrows, SCIP_Bool *improvement, SCIP_Bool *varboundserr, SCIP_HEURDATA *heurdata)
static	SCIP_DECL_HEUREXIT (heurExitTwoopt)
static	SCIP_DECL_HEURINITSOL (heurInitsolTwoopt)
static	SCIP_DECL_HEUREXITSOL (heurExitsolTwoopt)
static	SCIP_DECL_HEUREXEC (heurExecTwoopt)
SCIP_RETCODE	SCIPincludeHeurTwoopt (SCIP *scip)

Macro Definition Documentation

#define HEUR_NAME   "twoopt"

Definition at line 28 of file heur_twoopt.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and SCIPincludeHeurTwoopt().

#define HEUR_DESC   "primal heuristic to improve incumbent solution by flipping pairs of variables"

Definition at line 29 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_DISPCHAR   'B'

Definition at line 30 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_PRIORITY   -20100

Definition at line 31 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_FREQ   -1

Definition at line 32 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_FREQOFS   0

Definition at line 33 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_MAXDEPTH   -1

Definition at line 34 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 36 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 37 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define DEFAULT_INTOPT   FALSE

optional integer optimization is applied by default

Definition at line 40 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define DEFAULT_WAITINGNODES   0

default number of nodes to wait after current best solution before calling heuristic

Definition at line 41 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define DEFAULT_MATCHINGRATE   0.5

default percentage by which two variables have to match in their LP-row set to be associated as pair by heuristic

Definition at line 42 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define DEFAULT_MAXNSLAVES   199

default number of slave candidates for a master variable

Definition at line 44 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define DEFAULT_ARRAYSIZE   10

the default array size for temporary arrays

Definition at line 45 of file heur_twoopt.c.

Referenced by optimize().

Typedef Documentation

typedef enum Opttype OPTTYPE

Definition at line 105 of file heur_twoopt.c.

typedef enum Direction DIRECTION

Definition at line 113 of file heur_twoopt.c.

Enumeration Type Documentation

enum Opttype

Enumerator:

OPTTYPE_BINARY
OPTTYPE_INTEGER

Definition at line 100 of file heur_twoopt.c.

enum Direction

Enumerator:

DIRECTION_UP
DIRECTION_DOWN
DIRECTION_NONE
DIRECTION_UP
DIRECTION_DOWN

Definition at line 107 of file heur_twoopt.c.

Function Documentation

static SCIP_RETCODE shiftValues ( SCIP *  scip, SCIP_VAR *  master, SCIP_VAR *  slave, SCIP_Real  mastersolval, DIRECTION  masterdir, SCIP_Real  slavesolval, DIRECTION  slavedir, SCIP_Real  shiftval, SCIP_Real *  activities, int  nrows, SCIP_Bool *  feasible  )

static

tries to switch the values of two binary or integer variables and checks feasibility with respect to the LP.

Parameters

scip	scip instance
master	first variable of variable pair
slave	second variable of pair
mastersolval	current value of variable1 in solution
masterdir	the direction into which the master variable has to be shifted
slavesolval	current value of variable2 in solution
slavedir	the direction into which the slave variable has to be shifted
shiftval	the value that variables should be shifted by
activities	the LP-row activities
nrows	size of activities array
feasible	set to true if method has successfully switched the variable values

Definition at line 123 of file heur_twoopt.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by optimize().

static int varColCompare ( SCIP_VAR *  var1, SCIP_VAR *  var2  )

static

compare two variables with respect to their columns. Columns are treated as {0,1} vector, where every nonzero entry is treated as '1', and compared to each other lexicographically. I.e. var1 is < var2 if the corresponding column of var2 has the smaller single nonzero index of the two columns. This comparison costs O(constraints) in the worst case

Parameters

var1	left argument of comparison
var2	right argument of comparison

Definition at line 219 of file heur_twoopt.c.

References NULL, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIProwGetIndex(), and SCIPvarGetCol().

Referenced by SCIP_DECL_SORTPTRCOMP().

static SCIP_DECL_SORTPTRCOMP ( SCIPvarcolComp  )

static

implements a comparator to compare two variables with respect to their column entries

Definition at line 262 of file heur_twoopt.c.

References varColCompare().

static SCIP_Bool checkConstraintMatching ( SCIP *  scip, SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Real  matchingrate  )

static

checks if two given variables are contained in common LP rows, returns true if variables share the necessary percentage (matchingrate) of rows.

Parameters

scip	current SCIP instance
var1	first variable
var2	second variable
matchingrate	determines the ratio of shared LP rows compared to the total number of LP-rows each variable appears in

Definition at line 271 of file heur_twoopt.c.

References FALSE, MAX, NULL, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPisFeasLE(), SCIProwGetIndex(), SCIPvarGetCol(), and TRUE.

Referenced by innerPresolve().

static SCIP_Real determineBound ( SCIP *  scip, SCIP_SOL *  sol, SCIP_VAR *  master, DIRECTION  masterdirection, SCIP_VAR *  slave, DIRECTION  slavedirection, SCIP_Real *  activities, int  nrows  )

static

determines a bound by which the absolute solution value of two integer variables can be shifted at most. the criterion is the maintenance of feasibility of any global LP row. first implementation only considers shifting proportion 1:1, i.e. if master value is shifted by a certain integer value k downwards, the value of slave is simultaneously shifted by k upwards.

Parameters

scip	current scip instance
sol	current incumbent
master	current master variable
masterdirection	the shifting direction of the master variable
slave	slave variable with same LP_row set as master variable
slavedirection	the shifting direction of the slave variable
activities	array of LP row activities
nrows	the number of rows in LP and the size of the activities array

Definition at line 363 of file heur_twoopt.c.

References DIRECTION_DOWN, DIRECTION_UP, FALSE, MIN, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMessage, SCIPfeasFloor(), SCIPgetSolVal(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIProwGetIndex(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), and TRUE.

Referenced by optimize().

static void disposeVariable ( SCIP_VAR **  vars, int *  blockend, int  varindex  )

static

disposes variable with no heuristic relevancy, e.g., due to a fixed solution value, from its neighborhood block. The affected neighborhood block is reduced by 1.

Parameters

vars	problem variables
blockend	contains end index of block
varindex	variable index

Definition at line 586 of file heur_twoopt.c.

References NULL.

Referenced by optimize().

static SCIP_RETCODE innerPresolve ( SCIP *  scip, SCIP_VAR **  vars, SCIP_VAR ***  varspointer, int  nvars, int *  nblocks, int *  maxblocksize, int *  nblockvars, int **  blockstart, int **  blockend, SCIP_HEUR *  heur, SCIP_HEURDATA *  heurdata  )

static

realizes the presolve independently from type of variables it's applied to

Parameters

scip	current scip
vars	problem vars
varspointer	pointer to heuristic specific variable memory
nvars	the number of variables
nblocks	pointer to store the number of detected blocks
maxblocksize	maximum size of a block
nblockvars	pointer to store the number of block variables
blockstart	pointer to store the array of block start indices
blockend	pointer to store the array of block end indices
heur	the heuristic
heurdata	the heuristic data

Definition at line 602 of file heur_twoopt.c.

References checkConstraintMatching(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPreallocBlockMemoryArray, and SCIPsortPtr().

Referenced by presolveTwoOpt().

static SCIP_RETCODE presolveTwoOpt ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_HEURDATA *  heurdata  )

static

initializes the required structures for execution of heuristic. If objective coefficient functions are not all equal, each Binary and Integer variables are sorted into heuristic-specific arrays with respect to their lexicographical column order, where every zero in a column is interpreted as zero and every nonzero as '1'. After the sorting, the variables are compared with respect to user parameter matchingrate and the heuristic specific blocks are determined.

Parameters

scip	current scip instance
heur	heuristic
heurdata	the heuristic data

Definition at line 700 of file heur_twoopt.c.

References innerPresolve(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPgetVarsData(), SCIPheurSetData(), SCIPstatisticMessage, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyTwoopt  )

static

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

Definition at line 787 of file heur_twoopt.c.

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

static SCIP_DECL_HEURFREE ( heurFreeTwoopt  )

static

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

Definition at line 801 of file heur_twoopt.c.

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

static SCIP_DECL_HEURINIT ( heurInitTwoopt  )

static

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

Definition at line 821 of file heur_twoopt.c.

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

static SCIP_RETCODE optimize ( SCIP *  scip, SCIP_SOL *  worksol, SCIP_VAR **  vars, int *  blockstart, int *  blockend, int  nblocks, OPTTYPE  opttype, SCIP_Real *  activities, int  nrows, SCIP_Bool *  improvement, SCIP_Bool *  varboundserr, SCIP_HEURDATA *  heurdata  )

static

Parameters

scip	current SCIP instance
worksol	working solution
vars	binary or integer variables
blockstart	contains start indices of blocks
blockend	contains end indices of blocks
nblocks	the number of blocks
opttype	are binaries or integers optimized
activities	the LP-row activities
nrows	the number of LP rows
improvement	was there a successful shift?
varboundserr	has the current incumbent already been cut off
heurdata	the heuristic data

Definition at line 880 of file heur_twoopt.c.

References DEFAULT_ARRAYSIZE, determineBound(), DIRECTION_DOWN, DIRECTION_NONE, DIRECTION_UP, disposeVariable(), FALSE, MIN, NULL, OPTTYPE_BINARY, OPTTYPE_INTEGER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetRandomInt(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPisZero(), SCIPreallocBufferArray, SCIPsetSolVal(), SCIPsortRealPtrPtrInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), shiftValues(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEUREXIT ( heurExitTwoopt  )

static

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

Definition at line 1249 of file heur_twoopt.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemoryArray, SCIPheurGetData(), SCIPheurSetData(), and SCIPstatisticMessage.

static SCIP_DECL_HEURINITSOL ( heurInitsolTwoopt  )

static

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

Definition at line 1342 of file heur_twoopt.c.

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

static SCIP_DECL_HEUREXITSOL ( heurExitsolTwoopt  )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 1375 of file heur_twoopt.c.

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

static SCIP_DECL_HEUREXEC ( heurExecTwoopt  )

static

execution method of primal heuristic

Definition at line 1439 of file heur_twoopt.c.

References FALSE, MIN, NULL, optimize(), OPTTYPE_BINARY, OPTTYPE_INTEGER, presolveTwoOpt(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPcolSort(), SCIPcreateSolCopy(), SCIPdebug, SCIPdebugMessage, SCIPendDive(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVarLbDive(), SCIPgetVars(), SCIPgetVarUbDive(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPlinkLPSol(), SCIPprintRow(), SCIPprintSol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPsolGetNodenum(), SCIPsolIsOriginal(), SCIPsolSetHeur(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPwarningMessage(), and TRUE.

SCIP_RETCODE SCIPincludeHeurTwoopt

(

SCIP *

scip

)

creates the twoopt primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1740 of file heur_twoopt.c.

References DEFAULT_INTOPT, DEFAULT_MATCHINGRATE, DEFAULT_MAXNSLAVES, DEFAULT_WAITINGNODES, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), SCIPsetHeurInitsol(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().