54#define HEUR_NAME "intshifting"
55#define HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving"
56#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
57#define HEUR_PRIORITY -10000
60#define HEUR_MAXDEPTH -1
61#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
62#define HEUR_USESSUBSCIP FALSE
64#define MAXSHIFTINGS 50
65#define WEIGHTFACTOR 1.1
66#define DEFAULT_RANDSEED 17
91 SCIP_Real oldminactivity,
92 SCIP_Real oldmaxactivity,
93 SCIP_Real newminactivity,
94 SCIP_Real newmaxactivity
133 if( oldviol != newviol )
233 delta = newsolval - oldsolval;
240 for(
r = 0;
r < ncolrows; ++
r )
251 SCIP_Real oldminactivity;
252 SCIP_Real oldmaxactivity;
253 SCIP_Real newminactivity;
254 SCIP_Real newmaxactivity;
264 newminactivity = oldminactivity + delta * colvals[
r];
271 newmaxactivity = oldmaxactivity + delta * colvals[
r];
279 newminactivity, newmaxactivity);
298 SCIP_Real rowactivity,
304 SCIP_Real* oldsolval,
311 SCIP_Real activitydelta;
312 SCIP_Real bestshiftscore;
313 SCIP_Real bestdeltaobj;
316 assert(direction == +1 || direction == -1);
339 for(
c = 0;
c < nrowcols; ++
c )
346 SCIP_Real shiftscore;
362 increase = (direction * val > 0.0);
378 if( shiftscore <= bestshiftscore )
385 assert(direction * val < 0.0);
392 assert(activitydelta/val < 0.0);
393 shiftval = solval + activitydelta/val;
394 assert(shiftval <= solval);
397 shiftval =
MAX(shiftval, lb);
403 assert(direction * val > 0.0);
410 assert(activitydelta/val > 0.0);
411 shiftval = solval + activitydelta/val;
412 assert(shiftval >= solval);
415 shiftval =
MIN(shiftval, ub);
423 if( (shiftscore < bestshiftscore || deltaobj < bestdeltaobj)
426 bestshiftscore = shiftscore;
427 bestdeltaobj = deltaobj;
430 *newsolval = shiftval;
451 SCIP_Real* oldsolval,
460 SCIP_Real bestdeltaobj;
485 if( nlocks >= maxnlocks )
488 deltaobj =
obj * (shiftval - solval);
492 bestdeltaobj = deltaobj;
495 *newsolval = shiftval;
501 if( nlocks >= maxnlocks )
504 deltaobj =
obj * (shiftval - solval);
508 bestdeltaobj = deltaobj;
511 *newsolval = shiftval;
544 for(
r = 0;
r < nrows; ++
r )
565 if( theviolrowpos >= 0 )
822 for(
c = 0;
c < nnonz && !(mininf && maxinf); ++
c )
835 else if( vals[
c] > 0.0 )
851 else if( vals[
c] < 0.0 )
920 SCIP_Bool oldsolvalisfrac;
923 SCIPdebugMsg(
scip,
"intshifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n",
959 SCIPdebugMsg(
scip,
"intshifting heuristic: try to fix violated row <%s>: %g <= [%g,%g] <= %g\n",
975 SCIPdebugMsg(
scip,
"intshifting heuristic: search rounding variable and try to stay feasible\n");
982 SCIPdebugMsg(
scip,
"intshifting heuristic: -> didn't find a shifting variable\n");
988 SCIPdebugMsg(
scip,
"intshifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n",
1010 if( oldsolvalisfrac )
1019 if(
obj > 0.0 && newsolval > oldsolval )
1021 else if(
obj < 0.0 && newsolval < oldsolval )
1027 minobj +=
obj * (newsolval - oldsolval);
1031 if( !oldsolvalisfrac )
1036 if( newsolval < oldsolval )
1053 SCIPdebugMsg(
scip,
"intshifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
1070 SCIPdebugMsg(
scip,
"shifted solution is potentially feasible -> solve LP to fix continuous variables\n");
1078 for( v = 0; v <
nvars; ++v )
1107 SCIPwarningMessage(
scip,
"Error while solving LP in Intshifting heuristic; LP solve terminated with code <%d>\n",retstat);
#define SCIP_LONGINT_FORMAT
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPincludeHeurIntshifting(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
int SCIPcolGetNLPNonz(SCIP_COL *col)
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_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(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)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
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 SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetNLPNonz(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)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
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_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
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)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(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 SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(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)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
static SCIP_RETCODE selectEssentialRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldminactivity, SCIP_Real oldmaxactivity, SCIP_Real newminactivity, SCIP_Real newmaxactivity)
static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)
SCIP_Real * maxactivities
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *minactivities, SCIP_Real *maxactivities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
SCIPfreeSol(scip, &heurdata->sol))
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIP_Real * minactivities
SCIPheurSetData(heur, heurdata)
static SCIP_RETCODE selectShifting(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *row, SCIP_Real rowactivity, int direction, SCIP_Real *nincreases, SCIP_Real *ndecreases, SCIP_Real increaseweight, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
assert(minobj< SCIPgetCutoffbound(scip))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPlinkLPSol(scip, sol))
LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variabl...
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
public methods for primal heuristics
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
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 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_HEUREXEC(x)
enum SCIP_Retcode SCIP_RETCODE