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"

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 45 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

#define DEFAULT_ARRAYSIZE 10

the default array size for temporary arrays

Definition at line 46 of file heur_twoopt.c.

Referenced by optimize().

Typedef Documentation

typedef enum Opttype OPTTYPE

Definition at line 107 of file heur_twoopt.c.

typedef enum Direction DIRECTION

Definition at line 116 of file heur_twoopt.c.

Enumeration Type Documentation

enum Opttype

indicator for optimizing for binaries or integer variables

Enumerator
OPTTYPE_BINARY
OPTTYPE_INTEGER

Definition at line 102 of file heur_twoopt.c.

enum Direction

indicator for direction of shifting variables

Enumerator
DIRECTION_UP
DIRECTION_DOWN
DIRECTION_NONE
DIRECTION_UP
DIRECTION_DOWN

Definition at line 110 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 127 of file heur_twoopt.c.

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

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 232 of file heur_twoopt.c.

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

Referenced by SCIP_DECL_SORTPTRCOMP(), and shiftValues().

static SCIP_DECL_SORTPTRCOMP ( SCIPvarcolComp )

static

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

Definition at line 275 of file heur_twoopt.c.

References checkConstraintMatching(), SCIP_Bool, and varColCompare().

Referenced by 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 284 of file heur_twoopt.c.

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

Referenced by innerPresolve(), and SCIP_DECL_SORTPTRCOMP().

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. The 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 376 of file heur_twoopt.c.

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

Referenced by checkConstraintMatching(), and 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 601 of file heur_twoopt.c.

References innerPresolve(), and NULL.

Referenced by determineBound(), and 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 616 of file heur_twoopt.c.

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

Referenced by disposeVariable(), and 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 715 of file heur_twoopt.c.

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

Referenced by innerPresolve(), and SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyTwoopt )

static

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

Definition at line 796 of file heur_twoopt.c.

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

Referenced by presolveTwoOpt().

static SCIP_DECL_HEURFREE ( heurFreeTwoopt )

static

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

Definition at line 810 of file heur_twoopt.c.

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

Referenced by SCIP_DECL_HEURCOPY().

static SCIP_DECL_HEURINIT ( heurInitTwoopt )

static

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

Definition at line 830 of file heur_twoopt.c.

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

Referenced by SCIP_DECL_HEURFREE().

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