heur_shiftandpropagate.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53 #define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"
66 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */
67 #define DEFAULT_NPROPROUNDS 10 /**< The default number of propagation rounds for each propagation used */
69 #define DEFAULT_CUTOFFBREAKER 15 /**< fixed maximum number of allowed cutoffs before the heuristic stops */
73 #define DEFAULT_COLLECTSTATS TRUE /**< should variable statistics be collected during probing? */
74 #define DEFAULT_STOPAFTERFEASIBLE TRUE /**< Should the heuristic stop calculating optimal shift values when no more rows are violated? */
76 #define DEFAULT_SELECTBEST FALSE /**< should the heuristic choose the best candidate in every round? (set to FALSE for static order)? */
77 #define DEFAULT_MAXCUTOFFQUOT 0.0 /**< maximum percentage of allowed cutoffs before stopping the heuristic */
78 #define SORTKEYS "nrtuv"/**< options sorting key: (n)orms down, norms (u)p, (v)iolated rows decreasing,
80 #define DEFAULT_NOZEROFIXING FALSE /**< should variables with a zero shifting value be delayed instead of being fixed? */
81 #define DEFAULT_FIXBINLOCKS TRUE /**< should binary variables with no locks in one direction be fixed to that direction? */
82 #define DEFAULT_BINLOCKSFIRST FALSE /**< should binary variables with no locks be preferred in the ordering? */
83 #define DEFAULT_NORMALIZE TRUE /**< should coefficients and left/right hand sides be normalized by max row coeff? */
84 #define DEFAULT_UPDATEWEIGHTS FALSE /**< should row weight be increased every time the row is violated? */
85 #define DEFAULT_IMPLISCONTINUOUS TRUE /**< should implicit integer variables be treated as continuous variables? */
86 #define DEFAULT_MINFIXINGRATELP 0.0 /**< minimum fixing rate over all variables (including continuous) to solve LP */
105 SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */
108 int cutoffbreaker; /**< the number of cutoffs before heuristic execution is stopped, or -1 for no
112 SCIP_Real maxcutoffquot; /**< maximum percentage of allowed cutoffs before stopping the heuristic */
113 SCIP_Real minfixingratelp; /**< minimum fixing rate over all variables (including continuous) to solve LP */
117 SCIP_Bool stopafterfeasible; /**< Should the heuristic stop calculating optimal shift values when no
120 SCIP_Bool nozerofixing; /**< should variables with a zero shifting value be delayed instead of being fixed? */
121 SCIP_Bool fixbinlocks; /**< should binary variables with no locks in one direction be fixed to that direction? */
122 SCIP_Bool binlocksfirst; /**< should binary variables with no locks be preferred in the ordering? */
123 SCIP_Bool normalize; /**< should coefficients and left/right hand sides be normalized by max row coeff? */
125 SCIP_Bool impliscontinuous; /**< should implicit integer variables be treated as continuous variables? */
126 SCIP_Bool selectbest; /**< should the heuristic choose the best candidate in every round? (set to FALSE for static order)? */
139 {
144 };
157 TRANSFORMSTATUS* transformstatus; /**< information about transform status of every discrete variable */
161 SCIP_Real* upperbounds; /**< the upper bounds of every non-continuous variable after transformation*/
162 SCIP_Real* transformshiftvals; /**< values by which original discrete variable bounds were shifted */
188 /** returns whether a given variable is counted as discrete, depending on the parameter impliscontinuous */
195 return SCIPvarIsIntegral(var) && (SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT || !impliscontinuous);
198 /** returns whether a given column is counted as discrete, depending on the parameter impliscontinuous */
205 return SCIPcolIsIntegral(col) && (!impliscontinuous || SCIPvarGetType(SCIPcolGetVar(col)) != SCIP_VARTYPE_IMPLINT);
413 /* if both lower and upper bound are -infinity and infinity, resp., this is reflected by a free transform status.
414 * If the lower bound is already zero, this is reflected by identity transform status. In both cases, none of the
444 /* determine the upper bound for this variable in heuristic transformation (lower bound is implicit; always 0) */
485 SCIPdebugMsg(scip, "Variable <%s> at colpos %d transformed. Status %d LB <%g> --> <%g>, UB <%g> --> <%g>\n",
486 SCIPvarGetName(var), colpos, matrix->transformstatus[colpos], lb, 0.0, ub, matrix->upperbounds[colpos]);
489 /** initializes copy of the original coefficient matrix and applies heuristic specific adjustments: normalizing row
490 * vectors, transforming variable domains such that lower bound is zero, and relaxing continuous variables.
607 /* modify the lhs and rhs w.r.t to the rows constant and normalize by 1-norm, i.e divide the lhs and rhs by the
621 * Maxval may be zero if the constraint contains no variables but is modifiable, hence not redundant
631 /* in case of empty rows with a 0 < lhs <= 0.0 or 0.0 <= rhs < 0 we deduce the infeasibility of the problem */
632 if( nrowlpnonz == 0 && (SCIPisFeasPositive(scip, matrix->lhs[i]) || SCIPisFeasNegative(scip, matrix->rhs[i])) )
686 /* loop over all rows with nonzero coefficients in the column, transform them and add them to the heuristic matrix */
737 SCIPdebugMsg(scip, "Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n",
816 if( violatedrowpos[rowindex] == -1 && (SCIPisFeasGT(scip, matrix->lhs[rowindex], 0.0) || SCIPisFeasLT(scip, matrix->rhs[rowindex], 0.0)) )
829 else if( violatedrowpos[rowindex] >= 0 && SCIPisFeasLE(scip, matrix->lhs[rowindex], 0.0) && SCIPisFeasGE(scip, matrix->rhs[rowindex], 0.0) )
878 /* check if we requested an update for a single variable, or if we want to (re)-initialize the whole violation info */
909 checkRowViolation(scip, matrix, rowpos, violatedrows, violatedrowpos, nviolatedrows, rowweights, updateweights);
911 assert((violatedrowpos[rowpos] == -1 && SCIPisFeasGE(scip, matrix->rhs[rowpos], 0.0) && SCIPisFeasLE(scip, matrix->lhs[rowpos], 0.0))
912 || (violatedrowpos[rowpos] >= 0 &&(SCIPisFeasLT(scip, matrix->rhs[rowpos], 0.0) || SCIPisFeasGT(scip, matrix->lhs[rowpos], 0.0))));
934 /* check if original variable has different bounds and transform solution value correspondingly */
950 * @todo if there is already an incumbent solution, try considering the objective cutoff as additional constraint */
1013 /* for a feasible row, determine the minimum integer value within the bounds of the variable by which it has to be
1023 * i.e. a positive coefficient for a "<="-constraint, a negative coefficient for a ">="-constraint.
1030 /* if the variable has no lock in the current row, it can still help to increase the slack of this row;
1038 /* check if the least violating shift lies within variable bounds and set corresponding array values */
1039 if( !SCIPisInfinity(scip, maxfeasshift) && SCIPisFeasLE(scip, maxfeasshift + 1.0, upperbound) )
1051 /* for a violated row, determine the minimum integral value within the bounds of the variable by which it has to be
1060 /* if coefficient has the right sign to make row feasible, determine the minimum integer to shift variable
1068 /* check if the minimum feasibility recovery shift lies within variable bounds and set corresponding array
1085 /* in case that the variable cannot affect the feasibility of any row, in particular it cannot violate
1105 /* best shifting step is calculated by summing up the violation changes for each relevant step and
1106 * taking the one which leads to the minimum sum. This sum measures the balance of feasibility recovering and
1108 * note, the sums for smaller steps have to be taken into account for all bigger steps, i.e., the sums can be
1115 /* if we reached the last entry for the current step value, we have finished computing its sum and
1130 /** updates transformation of a given variable by taking into account current local bounds. if the bounds have changed
1131 * since last update, updating the heuristic specific upper bound of the variable, its current transformed solution value
1159 SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1209 assert(matrix->transformstatus[varindex] == TRANSFORMSTATUS_LB || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1210 assert(SCIPisLE(scip, ABS(lb), ABS(ub)) || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1216 SCIPerrorMessage("Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n", status);
1220 /* if the bound, by which the variable was shifted, has changed, deltashift is different from zero, which requires
1233 /* go through rows, update the rows w.r.t. the influence of the changed transformation of the variable */
1250 checkViolations(scip, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1252 SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1261 {
1347 " SHIFTANDPROPAGATE PROBING : %d probings, %" SCIP_LONGINT_FORMAT " domain reductions, ncutoffs: %d , LP iterations: %" SCIP_LONGINT_FORMAT " \n ",
1357 /** initialization method of primal heuristic(called after problem was transformed). We only need this method for
1495 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1529 /* copy and sort the columns by their variable types (binary before integer before implicit integer before continuous) */
1536 /* we have to collect the number of different variable types before we start probing since during probing variable
1559 /* save the position of this column in the array such that it can be accessed as the "true" column position */
1574 /* this should always be fulfilled because we perform shift and propagate only at the root node */
1586 SCIP_CALL( initMatrix(scip, matrix, heurdata, colposs, heurdata->normalize, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1595 /* the number of discrete LP column variables can be less than the actual number of variables, if, e.g., there
1600 SCIPdebugMsg(scip, "Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1646 checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1657 /* sort variables w.r.t. the sorting key parameter. Sorting is indirect, all matrix column data
1709 SCIPdebugMsg(scip, "Variables sorted down w.r.t their number of currently infeasible rows!\n");
1726 SCIPdebugMsg(scip, "Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1788 /* if c reaches nbinwithoutlocks, then all binary variables without locks were sorted to the beginning of the array */
1837 assert((c < nbinwithoutlocks) == (SCIPvarIsBinary(SCIPcolGetVar(heurdata->lpcols[permutation[c]]))
1838 && (SCIPvarGetNLocksUpType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0
1839 || SCIPvarGetNLocksDownType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0)));
1861 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], NULL) );
1870 SCIPdebugMsg(scip, "SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1875 /* loop over variables, shift them according to shifting criteria and try to reduce the global infeasibility */
1926 SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex,lb, ub, violatedrows, violatedrowpos,
1931 SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1946 /* check whether the variable is binary and has no locks in one direction, so that we want to fix it to the
1963 /* only apply the computationally expensive best shift selection, if there is a violated row left */
1967 SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, 1, heurdata->rowweights, steps, violationchange,
1979 SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, -1, heurdata->rowweights, steps, violationchange,
1994 /* if zero optimal shift values are forbidden by the user parameter, delay the variable by marking it suspicious */
2010 /* if propagation is enabled, fix the variable to the new solution value and propagate the fixation
2015 /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2024 SCIPdebugMsg(scip, " Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2029 SCIPdebugMsg(scip, "Propagation finished! <%" SCIP_LONGINT_FORMAT "> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ? "CUTOFF" : "",
2042 if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot * SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2051 /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2056 /* if the variable upper and lower bound are equal to the solution value to which we tried to fix the variable,
2057 * we are trapped at an infeasible node and break; this can only happen due to an intermediate global bound change of the variable,
2060 if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
2065 else if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2067 /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2068 * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2079 else if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2081 /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2082 * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2095 /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
2103 /* since repropagation was successful, we indicate that this variable led to a cutoff in one direction */
2119 SCIPdebugMsg(scip, " Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2123 SCIPdebugMsg(scip, "Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2136 SCIPdebugMsg(scip, "Heuristic finished with %d remaining violations and %d remaining variables!\n",
2139 /* if constructed solution might be feasible, go through the queue of suspicious variables and set the solution
2159 /* update the transformation of the variable, since the bound might have changed after the last update. */
2161 SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex, SCIPvarGetLbLocal(var),
2164 /* retransform the solution value from the heuristic transformed space, set the solution value accordingly */
2170 SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) ); /* only to ensure that some assertions can be made later */
2172 SCIPdebugMsg(scip, " Remaining variable <%s> set to <%g>; %d Violations\n", SCIPvarGetName(var), origsolval,
2182 /* check if enough variables have been fixed (including continuous) to solve the remaining LP */
2235 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
2245 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
2251 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2257 * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
2258 * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2266 SCIPwarningMessage(scip, "Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2274 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2290 * None of integrality, feasibility of LP rows, variable bounds have to be checked, because they
2317 SCIPstatisticMessage(" Shiftandpropagate solution value: %16.9g \n", SCIPgetSolOrigObj(scip, sol));
2338 SCIP_CALL( SCIPdropVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], -1) );
2414 SCIP_CALL( updateTransformation(scip, matrix, eventhdlrdata->heurdata, colpos, lb, ub, eventhdlrdata->violatedrows,
2465 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/relax", "Should continuous variables be relaxed?",
2467 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/probing", "Should domains be reduced by probing?",
2472 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/cutoffbreaker", "The number of cutoffs before heuristic stops",
2475 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2477 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/sortvars", "Should variables be sorted for the heuristic?",
2479 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/collectstats", "should variable statistics be collected during probing?",
2506 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
Definition: type_result.h:33
Definition: type_result.h:47
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:438
preroot heuristic that alternatingly fixes variables and propagates domains
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
Definition: struct_scip.h:59
static void relaxVar(SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix, SCIP_Bool normalize)
Definition: heur_shiftandpropagate.c:283
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
Definition: heur_shiftandpropagate.c:1426
Definition: heur_shiftandpropagate.c:143
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
Definition: struct_var.h:198
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
static SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
Definition: heur_shiftandpropagate.c:2382
static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)
Definition: heur_shiftandpropagate.c:745
Definition: type_var.h:53
Definition: struct_misc.h:259
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
public methods for problem variables
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)
Definition: scip_heur.c:108
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: type_message.h:46
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:462
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
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)
Definition: scip_param.c:74
public methods for numerical tolerances
Definition: struct_lp.h:126
public methods for querying solving statistics
Definition: struct_sol.h:64
public methods for the branch-and-bound tree
static SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
Definition: heur_shiftandpropagate.c:1330
static SCIP_Bool varIsDiscrete(SCIP_VAR *var, SCIP_Bool impliscontinuous)
Definition: heur_shiftandpropagate.c:191
Definition: type_result.h:35
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
static void transformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)
Definition: heur_shiftandpropagate.c:386
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)
Definition: heur_shiftandpropagate.c:201
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
#define EVENTTYPE_SHIFTANDPROPAGATE
Definition: heur_shiftandpropagate.c:91
static SCIP_RETCODE initMatrix(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int *colposs, SCIP_Bool normalize, int *nmaxrows, SCIP_Bool relax, SCIP_Bool *initialized, SCIP_Bool *infeasible)
Definition: heur_shiftandpropagate.c:494
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
Definition: scip_probing.c:1035
Definition: type_var.h:42
Definition: type_retcode.h:33
public methods for primal CIP solutions
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
static SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
Definition: heur_shiftandpropagate.c:1362
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
Definition: struct_heur.h:88
Definition: type_lp.h:34
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
public data structures and miscellaneous methods
Definition: type_var.h:55
Definition: heur_shiftandpropagate.c:141
Definition: type_var.h:54
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10044
Definition: struct_lp.h:192
public methods for LP management
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
static void getColumnData(CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)
Definition: heur_shiftandpropagate.c:250
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)
Definition: scip_sol.c:3125
static void checkRowViolation(SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
Definition: heur_shiftandpropagate.c:793
public methods for the LP relaxation, rows and columns
static void checkViolations(SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
Definition: heur_shiftandpropagate.c:858
methods for sorting joint arrays of various types
public methods for managing events
general public methods
static SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
Definition: heur_shiftandpropagate.c:1412
static SCIP_Real retransformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)
Definition: heur_shiftandpropagate.c:919
SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)
Definition: heur_shiftandpropagate.c:2426
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
static SCIP_RETCODE updateTransformation(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int varindex, SCIP_Real lb, SCIP_Real ub, int *violatedrows, int *violatedrowpos, int *nviolatedrows)
Definition: heur_shiftandpropagate.c:1136
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:158
public methods for solutions
public methods for random numbers
public methods for the probing mode
static void getRowData(CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)
Definition: heur_shiftandpropagate.c:211
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
Definition: type_var.h:84
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850
Definition: heur_shiftandpropagate.c:142
static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
Definition: heur_shiftandpropagate.c:1261
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
Definition: heur_shiftandpropagate.c:144
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
Definition: type_lp.h:33
public methods for primal heuristics
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:561
SCIPallocBlockMemory(scip, subsol))
Definition: type_retcode.h:43
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:325
Definition: objbenders.h:33
public methods for global and local (sub)problems
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
static SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
Definition: heur_shiftandpropagate.c:1387
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)
Definition: scip_param.c:130
Definition: struct_event.h:195
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)
Definition: scip_param.c:48
static SCIP_RETCODE getOptimalShiftingValue(SCIP *scip, CONSTRAINTMATRIX *matrix, int varindex, int direction, int *rowweights, SCIP_Real *steps, int *violationchange, SCIP_Real *beststep, int *rowviolations)
Definition: heur_shiftandpropagate.c:953
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766
Definition: type_var.h:58