SCIP
Solving Constraint Integer Programs
heur_twoopt.c File Reference
Detailed Description
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_exact.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 |
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, 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
| #define HEUR_NAME "twoopt" |
Definition at line 56 of file heur_twoopt.c.
◆ HEUR_DESC
| #define HEUR_DESC "primal heuristic to improve incumbent solution by flipping pairs of variables" |
Definition at line 57 of file heur_twoopt.c.
◆ HEUR_DISPCHAR
| #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE |
Definition at line 58 of file heur_twoopt.c.
◆ HEUR_PRIORITY
| #define HEUR_PRIORITY -20100 |
Definition at line 59 of file heur_twoopt.c.
◆ HEUR_FREQ
| #define HEUR_FREQ -1 |
Definition at line 60 of file heur_twoopt.c.
◆ HEUR_FREQOFS
| #define HEUR_FREQOFS 0 |
Definition at line 61 of file heur_twoopt.c.
◆ HEUR_MAXDEPTH
| #define HEUR_MAXDEPTH -1 |
Definition at line 62 of file heur_twoopt.c.
◆ HEUR_TIMING
| #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 64 of file heur_twoopt.c.
◆ HEUR_USESSUBSCIP
| #define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 65 of file heur_twoopt.c.
◆ DEFAULT_INTOPT
| #define DEFAULT_INTOPT FALSE |
optional integer optimization is applied by default
Definition at line 68 of file heur_twoopt.c.
◆ DEFAULT_WAITINGNODES
| #define DEFAULT_WAITINGNODES 0 |
default number of nodes to wait after current best solution before calling heuristic
Definition at line 69 of file heur_twoopt.c.
◆ 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 71 of file heur_twoopt.c.
◆ DEFAULT_MAXNSLAVES
| #define DEFAULT_MAXNSLAVES 199 |
default number of slave candidates for a master variable
Definition at line 72 of file heur_twoopt.c.
◆ DEFAULT_ARRAYSIZE
| #define DEFAULT_ARRAYSIZE 10 |
the default array size for temporary arrays
Definition at line 73 of file heur_twoopt.c.
◆ DEFAULT_RANDSEED
| #define DEFAULT_RANDSEED 37 |
initial random seed
Definition at line 74 of file heur_twoopt.c.
Typedef Documentation
◆ OPTTYPE
Definition at line 134 of file heur_twoopt.c.
◆ DIRECTION
Definition at line 143 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 129 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 137 of file heur_twoopt.c.
Function Documentation
◆ shiftValues()
|
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 154 of file heur_twoopt.c.
References NULL, SCIP_OKAY, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by optimize().
◆ varColCompare()
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 257 of file heur_twoopt.c.
References NULL, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIProwGetIndex(), and SCIPvarGetCol().
Referenced by SCIP_DECL_SORTPTRCOMP().
◆ SCIP_DECL_SORTPTRCOMP()
|
static |
implements a comparator to compare two variables with respect to their column entries
Definition at line 299 of file heur_twoopt.c.
References varColCompare().
◆ checkConstraintMatching()
|
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 308 of file heur_twoopt.c.
References ABS, FALSE, MAX, NULL, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPisFeasLE(), SCIProwGetIndex(), SCIPvarGetCol(), and TRUE.
Referenced by innerPresolve().
◆ determineBound()
|
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 406 of file heur_twoopt.c.
References bound, DIRECTION_DOWN, DIRECTION_UP, FALSE, 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(), and TRUE.
Referenced by optimize().
◆ disposeVariable()
|
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 643 of file heur_twoopt.c.
References NULL.
Referenced by optimize().
◆ innerPresolve()
|
static |
realizes the presolve independently from type of variables it's applied to
- Parameters
-
scip current scip vars heuristic specific variables 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 658 of file heur_twoopt.c.
References checkConstraintMatching(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPreallocBlockMemoryArray, and SCIPsortPtr().
Referenced by presolveTwoOpt().
◆ 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.
- Parameters
-
scip current scip instance heur heuristic heurdata the heuristic data
Definition at line 754 of file heur_twoopt.c.
References FALSE, innerPresolve(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPgetNBinImplVars(), SCIPgetNBinVars(), SCIPgetNIntImplVars(), SCIPgetNIntVars(), SCIPgetVars(), SCIPheurSetData(), SCIPstatisticMessage, and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 873 of file heur_twoopt.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurTwoopt().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 887 of file heur_twoopt.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 907 of file heur_twoopt.c.
References DEFAULT_RANDSEED, FALSE, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurSetData(), and TRUE.
◆ optimize()
|
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 967 of file heur_twoopt.c.
References b, bound, 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, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisPositive(), SCIPisZero(), SCIPrandomGetInt(), SCIPreallocBufferArray, SCIPsetSolVal(), SCIPsortRealPtrPtrInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), shiftValues(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC(), and SPxexSCIP::trySolve().
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1326 of file heur_twoopt.c.
References NULL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemoryArray, SCIPfreeRandom(), SCIPheurGetData(), SCIPheurSetData(), and SCIPstatisticMessage.
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 1423 of file heur_twoopt.c.
References FALSE, HEUR_NAME, NULL, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 1456 of file heur_twoopt.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 1519 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_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPcolSort(), SCIPcreateSolCopy(), SCIPdebug, SCIPdebugMsg, SCIPendDive(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNContImplVars(), SCIPgetNContVars(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVarLbDive(), SCIPgetVars(), SCIPgetVarUbDive(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPinDive(), SCIPisExact(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPlinkLPSol(), SCIPprintRow(), SCIPprintSol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPsolGetNodenum(), SCIPsolIsOriginal(), SCIPsolSetHeur(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPstatisticMessage, SCIPtrySol(), SCIPunlinkSol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), SCIPwarningMessage(), and TRUE.