55#define HEUR_NAME "twoopt"
56#define HEUR_DESC "primal heuristic to improve incumbent solution by flipping pairs of variables"
57#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE
58#define HEUR_PRIORITY -20100
61#define HEUR_MAXDEPTH -1
63#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
64#define HEUR_USESSUBSCIP FALSE
67#define DEFAULT_INTOPT FALSE
68#define DEFAULT_WAITINGNODES 0
69#define DEFAULT_MATCHINGRATE 0.5
71#define DEFAULT_MAXNSLAVES 199
72#define DEFAULT_ARRAYSIZE 10
73#define DEFAULT_RANDSEED 37
83 SCIP_Real matchingrate;
311 SCIP_Real matchingrate
346 if( matchingrate == 0.0 )
584 SCIPdebugMsg(
scip,
" %g <= %g <= %g, bound = %g, effect = %g (%g * %d + %g * %d) (i=%d,j=%d)\n",
615 SCIPdebugMsg(
scip,
" No influence of row %s, effect %g, master coeff: %g slave coeff: %g (i=%d, j=%d)\n",
700 for(
int v = 1; v <
nvars; ++v )
712 (*blockend)[*nblocks] = v - 1;
723 (*blockend)[*nblocks] = v;
798 SCIPstatisticMessage(
" Twoopt BINARY presolving finished with <%d> blocks, <%d> block variables \n",
816 SCIPstatisticMessage(
" Twoopt Integer presolving finished with <%d> blocks, <%d> block variables \n",
969 for(
int b = 0;
b < nblocks; ++
b )
1000 SCIPdebugMsg(
scip,
"Solution has violated variable bounds for var %s: %g <= %g <= %g \n",
1038 for(
int s = 0; s <
nslaves; ++s )
1073 SCIPdebugMsg(
scip,
"Solution has violated variable bounds for var %s: %g <= %g <= %g \n",
1165 if(
npairs == arraysize )
1171 arraysize = 2 * arraysize;
1182 SCIPdebugMsg(
scip,
" Saved candidate pair {%s=%g, %s=%g} with objectives <%g>, <%g> to be set to {%g, %g} %d\n",
1237 SCIPdebugMsg(
scip,
" Promising candidates {%s=%g, %s=%g} with objectives <%g>, <%g> to be set to {%g, %g}\n",
1261 SCIPdebugMsg(
scip,
" Feasible shift: <%s>[%g, %g] (obj: %f) <%f> --> <%f>\n",
1266#ifdef SCIP_STATISTIC
1299#ifdef SCIP_STATISTIC
1302 " Twoopt Binary Statistics : "
1303 "%6.2g %6.2g %4.2g %4.0g %6d (blocks/run, variables/run, varpercentage, avg. block size, max block size) \n",
1311 " Twoopt Integer statistics : "
1312 "%6.2g %6.2g %4.2g %4.0g %6d (blocks/run, variables/run, varpercentage, avg block size, max block size) \n",
1320 " Twoopt results : "
1321 "%6d %6d %4d %4.2g (runs, binary exchanges, Integer shiftings, matching rate)\n",
1407#ifdef SCIP_STATISTIC
1605 SCIPdebugMsg(
scip,
" Twoopt heuristic has initialized activities and sorted rows! \n");
1655#ifdef SCIP_STATISTIC
1670 SCIPdebugMsg(
scip,
"shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
1677 SCIPdebugMsg(
scip,
" Cont. variable <%s>, status %d with bounds [%g <= %g <= x <= %g <= %g]\n",
1697 for(
int i = 0;
i < ndiscvars; ++
i )
1711 for(
int i = 0;
i < ndiscvars; ++
i )
1755#ifdef SCIP_STATISTIC
1810 "nodes to wait after last best solution before calling heuristic",
1819 "parameter to determine the percentage of rows two variables have to share before they are considered equal",
#define SCIP_LONGINT_FORMAT
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPincludeHeurTwoopt(SCIP *scip)
int SCIPcolGetNNonz(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
void SCIPcolSort(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
const char * SCIProwGetName(SCIP_ROW *row)
int SCIProwGetIndex(SCIP_ROW *row)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortRealPtrPtrInt(SCIP_Real *realarray, void **ptrarray1, void **ptrarray2, int *intarray, int len)
SCIPfreeSol(scip, &heurdata->sol))
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
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)
#define DEFAULT_MATCHINGRATE
#define DEFAULT_WAITINGNODES
static SCIP_Bool checkConstraintMatching(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real matchingrate)
static int varColCompare(SCIP_VAR *var1, SCIP_VAR *var2)
#define DEFAULT_ARRAYSIZE
#define DEFAULT_MAXNSLAVES
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 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 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_RETCODE presolveTwoOpt(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Primal heuristic to improve incumbent solution by flipping pairs of variables.
memory allocation routines
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for problem variables
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
#define SCIP_DECL_HEURINITSOL(x)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
#define SCIP_DECL_SORTPTRCOMP(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS