Scippy

SCIP

Solving Constraint Integer Programs

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"
#include "scip/pub_misc.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
 
#define DEFAULT_RANDSEED   37
 

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

◆ HEUR_NAME

◆ HEUR_DESC

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

Definition at line 30 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'B'

Definition at line 31 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -20100

Definition at line 32 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 33 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 34 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 35 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 37 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 38 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ DEFAULT_INTOPT

#define DEFAULT_INTOPT   FALSE

optional integer optimization is applied by default

Definition at line 41 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ DEFAULT_WAITINGNODES

#define DEFAULT_WAITINGNODES   0

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

Definition at line 42 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ DEFAULT_MATCHINGRATE

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

Referenced by SCIPincludeHeurTwoopt().

◆ DEFAULT_MAXNSLAVES

#define DEFAULT_MAXNSLAVES   199

default number of slave candidates for a master variable

Definition at line 46 of file heur_twoopt.c.

Referenced by SCIPincludeHeurTwoopt().

◆ DEFAULT_ARRAYSIZE

#define DEFAULT_ARRAYSIZE   10

the default array size for temporary arrays

Definition at line 47 of file heur_twoopt.c.

Referenced by optimize().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   37

initial random seed

Definition at line 48 of file heur_twoopt.c.

Referenced by SCIP_DECL_HEURINIT().

Typedef Documentation

◆ OPTTYPE

typedef enum Opttype OPTTYPE

Definition at line 108 of file heur_twoopt.c.

◆ DIRECTION

typedef enum Direction DIRECTION

Definition at line 117 of file heur_twoopt.c.

Enumeration Type Documentation

◆ Opttype

enum Opttype

indicator for optimizing for binaries or integer variables

Enumerator
OPTTYPE_BINARY 
OPTTYPE_INTEGER 

Definition at line 103 of file heur_twoopt.c.

◆ Direction

enum Direction

indicator for direction of shifting variables

Enumerator
DIRECTION_UP 
DIRECTION_DOWN 
DIRECTION_NONE 
DIRECTION_UP 
DIRECTION_DOWN 

Definition at line 111 of file heur_twoopt.c.

Function Documentation

◆ shiftValues()

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
scipscip instance
masterfirst variable of variable pair
slavesecond variable of pair
mastersolvalcurrent value of variable1 in solution
masterdirthe direction into which the master variable has to be shifted
slavesolvalcurrent value of variable2 in solution
slavedirthe direction into which the slave variable has to be shifted
shiftvalthe value that variables should be shifted by
activitiesthe LP-row activities
nrowssize of activities array
feasibleset to true if method has successfully switched the variable values

Definition at line 128 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().

◆ varColCompare()

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
var1left argument of comparison
var2right argument of comparison

Definition at line 233 of file heur_twoopt.c.

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

Referenced by SCIP_DECL_SORTPTRCOMP(), and shiftValues().

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

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

Referenced by varColCompare().

◆ checkConstraintMatching()

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
scipcurrent SCIP instance
var1first variable
var2second variable
matchingratedetermines the ratio of shared LP rows compared to the total number of LP-rows each variable appears in

Definition at line 285 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().

◆ determineBound()

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
scipcurrent scip instance
solcurrent incumbent
mastercurrent master variable
masterdirectionthe shifting direction of the master variable
slaveslave variable with same LP_row set as master variable
slavedirectionthe shifting direction of the slave variable
activitiesarray of LP row activities
nrowsthe number of rows in LP and the size of the activities array

Definition at line 377 of file heur_twoopt.c.

References bound, DIRECTION_DOWN, DIRECTION_UP, disposeVariable(), FALSE, MIN, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, 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().

◆ disposeVariable()

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
varsproblem variables
blockendcontains end index of block
varindexvariable index

Definition at line 601 of file heur_twoopt.c.

References innerPresolve(), and NULL.

Referenced by determineBound(), and optimize().

◆ innerPresolve()

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
scipcurrent scip
varsproblem vars
varspointerpointer to heuristic specific variable memory
nvarsthe number of variables
nblockspointer to store the number of detected blocks
maxblocksizemaximum size of a block
nblockvarspointer to store the number of block variables
blockstartpointer to store the array of block start indices
blockendpointer to store the array of block end indices
heurthe heuristic
heurdatathe 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().

◆ 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
scipcurrent scip instance
heurheuristic
heurdatathe 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().

◆ SCIP_DECL_HEURCOPY()

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

◆ SCIP_DECL_HEURFREE()

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, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

Referenced by SCIP_DECL_HEURCOPY().

◆ SCIP_DECL_HEURINIT()

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 DEFAULT_RANDSEED, FALSE, HEUR_NAME, NULL, optimize(), SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurSetData(), SCIPinitializeRandomSeed(), and SCIPrandomCreate().

Referenced by SCIP_DECL_HEURFREE().

◆ optimize()

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
scipcurrent SCIP instance
worksolworking solution
varsbinary or integer variables
blockstartcontains start indices of blocks
blockendcontains end indices of blocks
nblocksthe number of blocks
opttypeare binaries or integers optimized
activitiesthe LP-row activities
nrowsthe number of LP rows
improvementwas there a successful shift?
varboundserrhas the current incumbent already been cut off
heurdatathe heuristic data

Definition at line 890 of file heur_twoopt.c.

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

Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEURINIT().

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitTwoopt  )
static

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

Definition at line 1254 of file heur_twoopt.c.

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

Referenced by optimize().

◆ SCIP_DECL_HEURINITSOL()

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

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

Referenced by SCIP_DECL_HEUREXIT().

◆ SCIP_DECL_HEUREXITSOL()

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

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

Referenced by SCIP_DECL_HEURINITSOL().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecTwoopt  )
static