30 #define HEUR_NAME "shifting" 31 #define HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables" 32 #define HEUR_DISPCHAR 's' 33 #define HEUR_PRIORITY -5000 35 #define HEUR_FREQOFS 0 36 #define HEUR_MAXDEPTH -1 37 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP 38 #define HEUR_USESSUBSCIP FALSE 40 #define MAXSHIFTINGS 50 41 #define WEIGHTFACTOR 1.1 42 #define DEFAULT_RANDSEED 31 77 assert(violrows !=
NULL);
78 assert(violrowpos !=
NULL);
79 assert(nviolrows !=
NULL);
85 if( oldviol != newviol )
96 violpos = violrowpos[rowpos];
97 assert(0 <= violpos && violpos < *nviolrows);
98 assert(violrows[violpos] == row);
99 violrowpos[rowpos] = -1;
102 if( nfracsinrow[rowpos] > 0 )
104 assert(violpos < *nviolfracrows);
107 if( violpos != *nviolfracrows - 1 )
109 violrows[violpos] = violrows[*nviolfracrows - 1];
111 violpos = *nviolfracrows - 1;
116 assert(violpos >= *nviolfracrows);
119 if( violpos != *nviolrows - 1 )
121 violrows[violpos] = violrows[*nviolrows - 1];
129 assert(violrowpos[rowpos] == -1);
130 violrows[*nviolrows] = row;
131 violrowpos[rowpos] = *nviolrows;
137 if( nfracsinrow[rowpos] > 0 )
139 if( *nviolfracrows < *nviolrows - 1 )
143 violrows[*nviolrows - 1] = violrows[*nviolfracrows];
144 violrowpos[
SCIProwGetLPPos(violrows[*nviolrows - 1])] = *nviolrows - 1;
146 violrows[*nviolfracrows] = row;
147 violrowpos[rowpos] = *nviolfracrows;
178 assert(activities !=
NULL);
179 assert(nviolrows !=
NULL);
180 assert(0 <= *nviolrows && *nviolrows <= nlprows);
182 delta = newsolval - oldsolval;
187 assert(ncolrows == 0 || (colrows !=
NULL && colvals !=
NULL));
189 for( r = 0; r < ncolrows; ++r )
196 assert(-1 <= rowpos && rowpos < nlprows);
206 oldactivity = activities[rowpos];
209 newactivity = oldactivity + delta * colvals[r];
214 activities[rowpos] = newactivity;
217 updateViolations(scip, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldactivity, newactivity);
254 assert(direction == +1 || direction == -1);
255 assert(nincreases !=
NULL);
256 assert(ndecreases !=
NULL);
257 assert(shiftvar !=
NULL);
258 assert(oldsolval !=
NULL);
259 assert(newsolval !=
NULL);
277 for( c = 0; c < nrowcols; ++c )
297 increase = (direction * val > 0.0);
309 shiftscore = ndecreases[probindex]/increaseweight;
311 shiftscore = nincreases[probindex]/increaseweight;
316 if( shiftscore <= bestshiftscore )
323 assert(direction * val < 0.0);
330 assert(activitydelta/val < 0.0);
331 shiftval = solval + activitydelta/val;
332 assert(shiftval <= solval);
336 shiftval =
MAX(shiftval, lb);
342 assert(direction * val > 0.0);
349 assert(activitydelta/val > 0.0);
350 shiftval = solval + activitydelta/val;
351 assert(shiftval >= solval);
355 shiftval =
MIN(shiftval, ub);
361 ||
SCIPisEQ(scip, shiftval, solval) )
365 if( shiftscore < bestshiftscore || deltaobj < bestdeltaobj )
367 bestshiftscore = shiftscore;
368 bestdeltaobj = deltaobj;
371 *newsolval = shiftval;
406 assert(shiftvar !=
NULL);
407 assert(oldsolval !=
NULL);
408 assert(newsolval !=
NULL);
414 for( v = 0; v < nlpcands; ++v )
426 if( nlocks >= maxnlocks )
429 deltaobj = obj * (shiftval - solval);
430 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj <
SCIPgetCutoffbound(scip) )
433 bestdeltaobj = deltaobj;
436 *newsolval = shiftval;
442 if( nlocks >= maxnlocks )
445 deltaobj = obj * (shiftval - solval);
446 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj <
SCIPgetCutoffbound(scip) )
449 bestdeltaobj = deltaobj;
452 *newsolval = shiftval;
480 assert(nviolrows >= *nviolfracrows);
484 for( r = 0; r < nrows; ++r )
490 assert(0 <= rowlppos && rowlppos < nlprows);
497 nfracsinrow[rowlppos] += incval;
498 assert(nfracsinrow[rowlppos] >= 0);
499 theviolrowpos = violrowpos[rowlppos];
503 if( theviolrowpos >= 0 )
508 if( nfracsinrow[rowlppos] == 0 )
510 assert(theviolrowpos <= *nviolfracrows - 1);
514 if( theviolrowpos < *nviolfracrows - 1 )
516 violrows[theviolrowpos] = violrows[*nviolfracrows - 1];
517 violrows[*nviolfracrows - 1] = rows[r];
521 violrowpos[rowlppos] = *nviolfracrows - 1;
528 else if( nfracsinrow[rowlppos] == incval )
530 assert(theviolrowpos >= *nviolfracrows);
533 if( theviolrowpos > *nviolfracrows )
535 violrows[theviolrowpos] = violrows[*nviolfracrows];
536 violrows[*nviolfracrows] = rows[r];
540 violrowpos[rowlppos] = *nviolfracrows;
558 assert(heur !=
NULL);
580 heurdata->lastlp = -1;
601 assert(heurdata !=
NULL);
622 assert(heurdata !=
NULL);
623 heurdata->lastlp = -1;
656 int nnonimprovingshifts;
666 assert(result !=
NULL);
681 assert(heurdata !=
NULL);
685 if( nlps == heurdata->lastlp )
687 heurdata->lastlp = nlps;
693 if( nnodes % ((ncalls/100)/(nsolsfound+1)+1) != 0 )
710 SCIPdebugMsg(
scip,
"executing shifting heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
728 for( r = 0; r < nlprows; ++r )
741 violrows[nviolrows] = row;
742 violrowpos[r] = nviolrows;
754 for( c = 0; c < nlpcands; ++c )
755 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1);
767 for( c = 0; c < nlpcands; ++c )
771 minobj += obj * (bestshiftval - lpcandssol[c]);
775 nnonimprovingshifts = 0;
776 minnviolrows = INT_MAX;
777 increaseweight = 1.0;
778 while( (nfrac > 0 || nviolrows > 0) && nnonimprovingshifts <
MAXSHIFTINGS )
786 SCIPdebugMsg(
scip,
"shifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n",
790 nprevviolrows = nviolrows;
799 if( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts <
MAXSHIFTINGS-1) )
806 assert(nviolfracrows == 0 || nfrac > 0);
810 if( nviolfracrows > 0 )
811 rowidx = nviolfracrows - 1;
816 assert(0 <= rowidx && rowidx < nviolrows);
817 row = violrows[rowidx];
819 assert(0 <= rowpos && rowpos < nlprows);
820 assert(violrowpos[rowpos] == rowidx);
821 assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1);
823 SCIPdebugMsg(
scip,
"shifting heuristic: try to fix violated row <%s>: %g <= %g <= %g\n",
834 nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) );
837 if( shiftvar ==
NULL && nfrac > 0 )
839 SCIPdebugMsg(
scip,
"shifting heuristic: search rounding variable and try to stay feasible\n");
846 SCIPdebugMsg(
scip,
"shifting heuristic: -> didn't find a shifting variable\n");
850 SCIPdebugMsg(
scip,
"shifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n",
856 shiftvar, oldsolval, newsolval) );
857 if( nviolrows >= nprevviolrows )
858 nnonimprovingshifts++;
859 else if( nviolrows < minnviolrows )
861 minnviolrows = nviolrows;
862 nnonimprovingshifts = 0;
877 nnonimprovingshifts = 0;
878 minnviolrows = INT_MAX;
879 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1);
882 if( obj > 0.0 && newsolval > oldsolval )
884 else if( obj < 0.0 && newsolval < oldsolval )
890 minobj += obj * (newsolval - oldsolval);
894 if( !oldsolvalisfrac )
897 assert(0 <= probindex && probindex < nvars);
899 if( newsolval < oldsolval )
900 ndecreases[probindex] += increaseweight;
902 nincreases[probindex] += increaseweight;
903 if( increaseweight >= 1e+09 )
907 for( i = 0; i < nvars; ++i )
909 nincreases[i] /= increaseweight;
910 ndecreases[i] /= increaseweight;
912 increaseweight = 1.0;
916 SCIPdebugMsg(
scip,
"shifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
921 if( nfrac == 0 && nviolrows == 0 )
968 assert(heur !=
NULL);
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
static SCIP_DECL_HEUREXEC(heurExecShifting)
static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
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)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous v...
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)))
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_RETCODE SCIPincludeHeurShifting(SCIP *scip)
int SCIProwGetNLPNonz(SCIP_ROW *row)
static SCIP_DECL_HEURINITSOL(heurInitsolShifting)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldactivity, SCIP_Real newactivity)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
enum SCIP_Retcode SCIP_RETCODE
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)
#define SCIPfreeBufferArray(scip, ptr)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
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)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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 SCIP_DECL_HEURINIT(heurInitShifting)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
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 SCIPgetNVars(SCIP *scip)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
static SCIP_DECL_HEURCOPY(heurCopyShifting)
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 SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
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)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_DECL_HEUREXIT(heurExitShifting)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)