29 #define HEUR_NAME "rounding" 30 #define HEUR_DESC "LP rounding heuristic with infeasibility recovering" 31 #define HEUR_DISPCHAR 'R' 32 #define HEUR_PRIORITY -1000 34 #define HEUR_FREQOFS 0 35 #define HEUR_MAXDEPTH -1 36 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP 37 #define HEUR_USESSUBSCIP FALSE 39 #define DEFAULT_SUCCESSFACTOR 100 42 #define DEFAULT_ONCEPERNODE FALSE 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;
100 if( violpos != *nviolrows-1 )
102 violrows[violpos] = violrows[*nviolrows-1];
110 assert(violrowpos[rowpos] == -1);
111 violrows[*nviolrows] = row;
112 violrowpos[rowpos] = *nviolrows;
139 assert(activities != NULL);
140 assert(nviolrows != NULL);
141 assert(0 <= *nviolrows && *nviolrows <= nlprows);
143 delta = newsolval - oldsolval;
148 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
150 for( r = 0; r < ncolrows; ++r )
157 assert(-1 <= rowpos && rowpos < nlprows);
167 oldactivity = activities[rowpos];
170 newactivity = oldactivity + delta * colvals[r];
175 activities[rowpos] = newactivity;
178 updateViolations(scip, row, violrows, violrowpos, nviolrows, oldactivity, newactivity);
218 assert(direction == +1 || direction == -1);
219 assert(roundvar != NULL);
220 assert(oldsolval != NULL);
221 assert(newsolval != NULL);
232 for( c = 0; c < nrowcols; ++c )
247 if( direction * val < 0.0 )
251 if( nlocks <= minnlocks )
254 deltaobj = obj * (roundval - solval);
255 if( (nlocks < minnlocks || deltaobj < bestdeltaobj) && minobj - obj <
SCIPgetCutoffbound(scip) )
258 bestdeltaobj = deltaobj;
261 *newsolval = roundval;
268 assert(direction * val > 0.0);
270 if( nlocks <= minnlocks )
273 deltaobj = obj * (roundval - solval);
274 if( (nlocks < minnlocks || deltaobj < bestdeltaobj) && minobj + obj <
SCIPgetCutoffbound(scip) )
277 bestdeltaobj = deltaobj;
280 *newsolval = roundval;
303 return selectRounding(scip, sol, minobj, row, +1, roundvar, oldsolval, newsolval);
318 return selectRounding(scip, sol, minobj, row, -1, roundvar, oldsolval, newsolval);
348 assert(roundvar != NULL);
349 assert(oldsolval != NULL);
350 assert(newsolval != NULL);
356 for( v = 0; v < nlpcands; ++v )
368 if( nlocks >= maxnlocks )
371 deltaobj = obj * (roundval - solval);
372 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj <
SCIPgetCutoffbound(scip) )
375 bestdeltaobj = deltaobj;
378 *newsolval = roundval;
384 if( nlocks >= maxnlocks )
387 deltaobj = obj * (roundval - solval);
388 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj <
SCIPgetCutoffbound(scip) )
391 bestdeltaobj = deltaobj;
394 *newsolval = roundval;
412 assert(scip != NULL);
413 assert(heur != NULL);
428 assert(heur != NULL);
430 assert(scip != NULL);
434 assert(heurdata != NULL);
450 assert(heurdata != NULL);
454 heurdata->lastlp = -1;
469 assert(heurdata != NULL);
484 assert(heurdata != NULL);
485 heurdata->lastlp = -1;
488 if( heurdata->oncepernode )
532 assert(scip != NULL);
533 assert(result != NULL);
548 assert(heurdata != NULL);
552 if( nlps == heurdata->lastlp )
554 heurdata->lastlp = nlps;
560 if( nnodes % ((ncalls/heurdata->successfactor)/(nsolsfound+1)+1) != 0 )
576 SCIPdebugMsg(scip,
"executing rounding heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
587 for( r = 0; r < nlprows; ++r )
600 violrows[nviolrows] = row;
601 violrowpos[r] = nviolrows;
619 for( c = 0; c < nlpcands; ++c )
623 minobj += obj * (bestroundval - lpcandssol[c]);
633 SCIPdebugMsg(scip,
"rounding heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
649 row = violrows[nviolrows-1];
651 assert(0 <= rowpos && rowpos < nlprows);
652 assert(violrowpos[rowpos] == nviolrows-1);
654 SCIPdebugMsg(scip,
"rounding heuristic: try to fix violated row <%s>: %g <= %g <= %g\n",
670 SCIPdebugMsg(scip,
"rounding heuristic: search rounding variable and try to stay feasible\n");
675 if( roundvar == NULL )
677 SCIPdebugMsg(scip,
"rounding heuristic: -> didn't find a rounding variable\n");
681 SCIPdebugMsg(scip,
"rounding heuristic: -> round var <%s>, oldval=%g, newval=%g, obj=%g\n",
686 roundvar, oldsolval, newsolval) );
694 if( obj > 0.0 && newsolval > oldsolval )
696 else if( obj < 0.0 && newsolval < oldsolval )
699 SCIPdebugMsg(scip,
"rounding heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
704 if( nfrac == 0 && nviolrows == 0 )
718 SCIPdebugMsg(scip,
"found feasible rounded solution:\n");
754 assert(heur != NULL);
766 "number of calls per found solution that are considered as standard success, a higher factor causes the heuristic to be called more often",
770 "should the heuristic only be called once per node?",
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
static SCIP_DECL_HEUREXEC(heurExecRounding)
static SCIP_RETCODE selectDecreaseRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
#define DEFAULT_SUCCESSFACTOR
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
LP rounding heuristic that tries to recover from intermediate infeasibilities.
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
const char * SCIProwGetName(SCIP_ROW *row)
static SCIP_RETCODE selectRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, int direction, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
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)
#define SCIPfreeBufferArray(scip, ptr)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
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)
static SCIP_DECL_HEURINITSOL(heurInitsolRounding)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
#define DEFAULT_ONCEPERNODE
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_RETCODE SCIPincludeHeurRounding(SCIP *scip)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
#define SCIP_HEURTIMING_AFTERLPNODE
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
const char * SCIPvarGetName(SCIP_VAR *var)
static SCIP_DECL_HEUREXITSOL(heurExitsolRounding)
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)
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
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)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
static SCIP_DECL_HEUREXIT(heurExitRounding)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
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)
static SCIP_RETCODE selectEssentialRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
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 SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
static SCIP_DECL_HEURFREE(heurFreeRounding)
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)
static SCIP_DECL_HEURCOPY(heurCopyRounding)
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, SCIP_Real oldactivity, SCIP_Real newactivity)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
enum SCIP_Vartype SCIP_VARTYPE
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
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_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_RETCODE selectIncreaseRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
static SCIP_DECL_HEURINIT(heurInitRounding)
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_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)