primal heuristic to improve incumbent solution by flipping pairs of variables
Definition in file heur_twoopt.c.
#include "blockmemshell/memory.h"
#include "scip/heur_twoopt.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.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_prob.h"
#include "scip/scip_randnumgen.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 "twoopt" |
#define | HEUR_DESC "primal heuristic to improve incumbent solution by flipping pairs of variables" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE |
#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 |
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) |
#define HEUR_NAME "twoopt" |
Definition at line 55 of file heur_twoopt.c.
#define HEUR_DESC "primal heuristic to improve incumbent solution by flipping pairs of variables" |
Definition at line 56 of file heur_twoopt.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE |
Definition at line 57 of file heur_twoopt.c.
#define HEUR_PRIORITY -20100 |
Definition at line 58 of file heur_twoopt.c.
#define HEUR_FREQ -1 |
Definition at line 59 of file heur_twoopt.c.
#define HEUR_FREQOFS 0 |
Definition at line 60 of file heur_twoopt.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 61 of file heur_twoopt.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 63 of file heur_twoopt.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 64 of file heur_twoopt.c.
#define DEFAULT_INTOPT FALSE |
optional integer optimization is applied by default
Definition at line 67 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 68 of file heur_twoopt.c.
#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 69 of file heur_twoopt.c.
Referenced by SCIPincludeHeurTwoopt().
#define DEFAULT_MAXNSLAVES 199 |
default number of slave candidates for a master variable
Definition at line 71 of file heur_twoopt.c.
Referenced by SCIPincludeHeurTwoopt().
#define DEFAULT_ARRAYSIZE 10 |
the default array size for temporary arrays
Definition at line 72 of file heur_twoopt.c.
Referenced by optimize().
#define DEFAULT_RANDSEED 37 |
initial random seed
Definition at line 73 of file heur_twoopt.c.
Definition at line 133 of file heur_twoopt.c.
Definition at line 142 of file heur_twoopt.c.
enum Opttype |
indicator for optimizing for binaries or integer variables
Enumerator | |
---|---|
OPTTYPE_BINARY | |
OPTTYPE_INTEGER |
Definition at line 128 of file heur_twoopt.c.
enum Direction |
indicator for direction of shifting variables
Enumerator | |
---|---|
DIRECTION_UP | |
DIRECTION_DOWN | |
DIRECTION_NONE |
Definition at line 136 of file heur_twoopt.c.
|
static |
Tries to switch the values of two binary or integer variables and checks feasibility with respect to the LP.
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 153 of file heur_twoopt.c.
References activities, assert(), i, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by optimize().
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
var1 | left argument of comparison |
var2 | right argument of comparison |
Definition at line 256 of file heur_twoopt.c.
References assert(), i, NULL, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIProwGetIndex(), and SCIPvarGetCol().
Referenced by SCIP_DECL_SORTPTRCOMP().
|
static |
implements a comparator to compare two variables with respect to their column entries
Definition at line 298 of file heur_twoopt.c.
References varColCompare().
|
static |
checks if two given variables are contained in common LP rows, returns true if variables share the necessary percentage (matchingrate) of rows.
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 307 of file heur_twoopt.c.
References ABS, assert(), FALSE, i, MAX, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPisFeasLE(), SCIProwGetIndex(), SCIPvarGetCol(), and TRUE.
Referenced by innerPresolve().
|
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.
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 405 of file heur_twoopt.c.
References activities, assert(), bound, DIRECTION_DOWN, DIRECTION_UP, FALSE, i, MAX, MIN, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasGE(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIProwGetIndex(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), sol, and TRUE.
Referenced by optimize().
|
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.
vars | problem variables |
blockend | contains end index of block |
varindex | variable index |
Definition at line 642 of file heur_twoopt.c.
References assert(), NULL, and vars.
Referenced by optimize().
|
static |
realizes the presolve independently from type of variables it's applied to
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 657 of file heur_twoopt.c.
References assert(), checkConstraintMatching(), heurdata, MAX, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPreallocBlockMemoryArray, SCIPsortPtr(), and vars.
Referenced by presolveTwoOpt().
|
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.
scip | current scip instance |
heur | heuristic |
heurdata | the heuristic data |
Definition at line 757 of file heur_twoopt.c.
References assert(), heurdata, innerPresolve(), MAX, nbinvars, nintvars, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPgetVarsData(), SCIPheurSetData(), SCIPstatisticMessage, TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 842 of file heur_twoopt.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurTwoopt().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 856 of file heur_twoopt.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 876 of file heur_twoopt.c.
References assert(), DEFAULT_RANDSEED, FALSE, HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurSetData(), and TRUE.
|
static |
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 936 of file heur_twoopt.c.
References activities, assert(), b, bound, DEFAULT_ARRAYSIZE, determineBound(), DIRECTION_DOWN, DIRECTION_NONE, DIRECTION_UP, disposeVariable(), FALSE, heurdata, MIN, NULL, OPTTYPE_BINARY, OPTTYPE_INTEGER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisPositive(), SCIPisZero(), SCIPrandomGetInt(), SCIPreallocBufferArray, SCIPsetSolVal(), SCIPsortRealPtrPtrInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), shiftValues(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1295 of file heur_twoopt.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemoryArray, SCIPfreeRandom(), SCIPheurGetData(), SCIPheurSetData(), and SCIPstatisticMessage.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 1392 of file heur_twoopt.c.
References assert(), FALSE, HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 1425 of file heur_twoopt.c.
References assert(), HEUR_NAME, heurdata, nbinvars, nintvars, NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
execution method of primal heuristic
Definition at line 1488 of file heur_twoopt.c.
References activities, assert(), FALSE, heurdata, i, lperror, lprows, MIN, nbinvars, nintvars, nlprows, NULL, optimize(), OPTTYPE_BINARY, OPTTYPE_INTEGER, presolveTwoOpt(), result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPcolSort(), SCIPcreateSolCopy(), SCIPdebug, SCIPdebugMsg, 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.