30 #define HEUR_NAME "intshifting" 31 #define HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving" 32 #define HEUR_DISPCHAR 'i' 33 #define HEUR_PRIORITY -10000 35 #define HEUR_FREQOFS 0 36 #define HEUR_MAXDEPTH -1 37 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 38 #define HEUR_USESSUBSCIP FALSE 40 #define MAXSHIFTINGS 50 41 #define WEIGHTFACTOR 1.1 42 #define DEFAULT_RANDSEED 17 78 assert(violrows !=
NULL);
79 assert(violrowpos !=
NULL);
80 assert(nviolrows !=
NULL);
86 if( oldviol != newviol )
97 violpos = violrowpos[rowpos];
98 assert(0 <= violpos && violpos < *nviolrows);
99 assert(violrows[violpos] == row);
100 violrowpos[rowpos] = -1;
102 if( nfracsinrow[rowpos] > 0 )
104 violrows[violpos] = violrows[*nviolrows-1];
105 assert(violpos < *nviolfracrows);
108 if( violpos != *nviolfracrows - 1 )
110 violrows[violpos] = violrows[*nviolfracrows - 1];
112 violpos = *nviolfracrows - 1;
117 assert(violpos >= *nviolfracrows);
120 if( violpos != *nviolrows - 1 )
122 violrows[violpos] = violrows[*nviolrows - 1];
130 assert(violrowpos[rowpos] == -1);
131 violrows[*nviolrows] = row;
132 violrowpos[rowpos] = *nviolrows;
138 if( nfracsinrow[rowpos] > 0 )
140 if( *nviolfracrows < *nviolrows - 1 )
144 violrows[*nviolrows - 1] = violrows[*nviolfracrows];
145 violrowpos[
SCIProwGetLPPos(violrows[*nviolrows - 1])] = *nviolrows - 1;
147 violrows[*nviolfracrows] = row;
148 violrowpos[rowpos] = *nviolfracrows;
180 assert(minactivities !=
NULL);
181 assert(maxactivities !=
NULL);
182 assert(nviolrows !=
NULL);
183 assert(0 <= *nviolrows && *nviolrows <= nlprows);
186 delta = newsolval - oldsolval;
191 assert(ncolrows == 0 || (colrows !=
NULL && colvals !=
NULL));
193 for( r = 0; r < ncolrows; ++r )
200 assert(-1 <= rowpos && rowpos < nlprows);
212 oldminactivity = minactivities[rowpos];
213 oldmaxactivity = maxactivities[rowpos];
217 newminactivity = oldminactivity + delta * colvals[r];
218 minactivities[rowpos] = newminactivity;
224 newmaxactivity = oldmaxactivity + delta * colvals[r];
225 maxactivities[rowpos] = newmaxactivity;
231 updateViolations(scip, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldminactivity, oldmaxactivity,
232 newminactivity, newmaxactivity);
269 assert(direction == +1 || direction == -1);
270 assert(nincreases !=
NULL);
271 assert(ndecreases !=
NULL);
272 assert(shiftvar !=
NULL);
273 assert(oldsolval !=
NULL);
274 assert(newsolval !=
NULL);
292 for( c = 0; c < nrowcols; ++c )
315 increase = (direction * val > 0.0);
325 shiftscore = ndecreases[probindex]/increaseweight;
327 shiftscore = nincreases[probindex]/increaseweight;
331 if( shiftscore <= bestshiftscore )
338 assert(direction * val < 0.0);
345 assert(activitydelta/val < 0.0);
346 shiftval = solval + activitydelta/val;
347 assert(shiftval <= solval);
350 shiftval =
MAX(shiftval, lb);
356 assert(direction * val > 0.0);
363 assert(activitydelta/val > 0.0);
364 shiftval = solval + activitydelta/val;
365 assert(shiftval >= solval);
368 shiftval =
MIN(shiftval, ub);
372 if(
SCIPisEQ(scip, shiftval, solval) )
376 if( shiftscore < bestshiftscore || deltaobj < bestdeltaobj )
378 bestshiftscore = shiftscore;
379 bestdeltaobj = deltaobj;
382 *newsolval = shiftval;
417 assert(shiftvar !=
NULL);
418 assert(oldsolval !=
NULL);
419 assert(newsolval !=
NULL);
425 for( v = 0; v < nlpcands; ++v )
437 if( nlocks >= maxnlocks )
440 deltaobj = obj * (shiftval - solval);
441 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj <
SCIPgetCutoffbound(scip) )
444 bestdeltaobj = deltaobj;
447 *newsolval = shiftval;
453 if( nlocks >= maxnlocks )
456 deltaobj = obj * (shiftval - solval);
457 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj <
SCIPgetCutoffbound(scip) )
460 bestdeltaobj = deltaobj;
463 *newsolval = shiftval;
491 assert(nviolrows >= *nviolfracrows);
496 for( r = 0; r < nrows; ++r )
505 assert(0 <= rowlppos && rowlppos < nlprows);
511 nfracsinrow[rowlppos] += incval;
512 assert(nfracsinrow[rowlppos] >= 0);
514 theviolrowpos = violrowpos[rowlppos];
517 if( theviolrowpos >= 0 )
522 if( nfracsinrow[rowlppos] == 0 )
524 assert(theviolrowpos <= *nviolfracrows - 1);
528 if( theviolrowpos < *nviolfracrows - 1 )
530 violrows[theviolrowpos] = violrows[*nviolfracrows - 1];
531 violrows[*nviolfracrows - 1] = row;
535 violrowpos[rowlppos] = *nviolfracrows - 1;
542 else if( nfracsinrow[rowlppos] == incval )
544 assert(theviolrowpos >= *nviolfracrows);
547 if( theviolrowpos > *nviolfracrows )
549 violrows[theviolrowpos] = violrows[*nviolfracrows];
550 violrows[*nviolfracrows] = row;
554 violrowpos[rowlppos] = *nviolfracrows;
572 assert(heur !=
NULL);
594 heurdata->lastlp = -1;
614 assert(heurdata !=
NULL);
635 assert(heurdata !=
NULL);
636 heurdata->lastlp = -1;
670 int nnonimprovingshifts;
680 assert(result !=
NULL);
705 assert(heurdata !=
NULL);
709 if( nlps == heurdata->lastlp )
711 heurdata->lastlp = nlps;
717 if( nnodes % (ncalls/(nsolsfound+1)+1) != 0 )
734 SCIPdebugMsg(
scip,
"executing intshifting heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
754 for( r = 0; r < nlprows; ++r )
771 minactivities[r] = 0.0;
772 maxactivities[r] = 0.0;
776 for( c = 0; c < nnonz && !(mininf && maxinf); ++c )
786 minactivities[r] += act;
787 maxactivities[r] += act;
789 else if( vals[c] > 0.0 )
799 minactivities[r] += vals[c] * lb;
803 maxactivities[r] += vals[c] * ub;
805 else if( vals[c] < 0.0 )
815 minactivities[r] += vals[c] * ub;
819 maxactivities[r] += vals[c] * lb;
831 violrows[nviolrows] = row;
832 violrowpos[r] = nviolrows;
845 for( c = 0; c < nlpcands; ++c )
846 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1);
858 for( c = 0; c < nlpcands; ++c )
862 minobj += obj * (bestshiftval - lpcandssol[c]);
866 nnonimprovingshifts = 0;
867 minnviolrows = INT_MAX;
868 increaseweight = 1.0;
877 SCIPdebugMsg(
scip,
"intshifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n",
881 nprevviolrows = nviolrows;
890 if( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts <
MAXSHIFTINGS-1) )
897 assert(nviolfracrows == 0 || nfrac > 0);
901 if( nviolfracrows > 0 )
902 rowidx = nviolfracrows - 1;
906 assert(0 <= rowidx && rowidx < nviolrows);
907 row = violrows[rowidx];
909 assert(0 <= rowpos && rowpos < nlprows);
910 assert(violrowpos[rowpos] == rowidx);
911 assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1);
913 SCIPdebugMsg(
scip,
"intshifting heuristic: try to fix violated row <%s>: %g <= [%g,%g] <= %g\n",
924 direction, nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) );
927 if( shiftvar ==
NULL && nfrac > 0 )
929 SCIPdebugMsg(
scip,
"intshifting heuristic: search rounding variable and try to stay feasible\n");
936 SCIPdebugMsg(
scip,
"intshifting heuristic: -> didn't find a shifting variable\n");
942 SCIPdebugMsg(
scip,
"intshifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n",
948 nfracsinrow, nlprows, shiftvar, oldsolval, newsolval) );
950 if( nviolrows >= nprevviolrows )
951 nnonimprovingshifts++;
952 else if( nviolrows < minnviolrows )
954 minnviolrows = nviolrows;
955 nnonimprovingshifts = 0;
964 if( oldsolvalisfrac )
968 nnonimprovingshifts = 0;
969 minnviolrows = INT_MAX;
970 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1);
973 if( obj > 0.0 && newsolval > oldsolval )
975 else if( obj < 0.0 && newsolval < oldsolval )
981 minobj += obj * (newsolval - oldsolval);
985 if( !oldsolvalisfrac )
988 assert(0 <= probindex && probindex < nvars);
990 if( newsolval < oldsolval )
991 ndecreases[probindex] += increaseweight;
993 nincreases[probindex] += increaseweight;
994 if( increaseweight >= 1e+09 )
998 for( i = 0; i < nvars; ++i )
1000 nincreases[i] /= increaseweight;
1001 ndecreases[i] /= increaseweight;
1003 increaseweight = 1.0;
1007 SCIPdebugMsg(
scip,
"intshifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
1014 if( nfrac == 0 && nviolrows == 0 )
1024 SCIPdebugMsg(
scip,
"shifted solution is potentially feasible -> solve LP to fix continuous variables\n");
1032 for( v = 0; v < nvars; ++v )
1040 for( v = 0; v < nintvars; ++v )
1061 SCIPwarningMessage(
scip,
"Error while solving LP in Intshifting heuristic; LP solve terminated with code <%d>\n",retstat);
1125 assert(heur !=
NULL);
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEUREXEC(heurExecIntshifting)
const char * SCIProwGetName(SCIP_ROW *row)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
enum SCIP_Retcode SCIP_RETCODE
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)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
int SCIPvarGetProbindex(SCIP_VAR *var)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIPfreeBlockMemory(scip, ptr)
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)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeHeurIntshifting(SCIP *scip)
#define SCIPfreeBufferArray(scip, ptr)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
int SCIPgetNContVars(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURINIT(heurInitIntshifting)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
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)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
static SCIP_DECL_HEUREXIT(heurExitIntshifting)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
public data structures and miscellaneous methods
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
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)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
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)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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)
int SCIPgetNBinVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
static SCIP_DECL_HEURCOPY(heurCopyIntshifting)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variabl...
SCIP_RETCODE SCIPendDive(SCIP *scip)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
static SCIP_DECL_HEURINITSOL(heurInitsolIntshifting)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)