heur_shiftandpropagate.c
Go to the documentation of this file.
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62#define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"
75#define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */
76#define DEFAULT_NPROPROUNDS 10 /**< The default number of propagation rounds for each propagation used */
78#define DEFAULT_CUTOFFBREAKER 15 /**< fixed maximum number of allowed cutoffs before the heuristic stops */
83#define DEFAULT_STOPAFTERFEASIBLE TRUE /**< Should the heuristic stop calculating optimal shift values when no more rows are violated? */
85#define DEFAULT_SELECTBEST FALSE /**< should the heuristic choose the best candidate in every round? (set to FALSE for static order)? */
86#define DEFAULT_MAXCUTOFFQUOT 0.0 /**< maximum percentage of allowed cutoffs before stopping the heuristic */
87#define SORTKEYS "nrtuv"/**< options sorting key: (n)orms down, norms (u)p, (v)iolated rows decreasing,
89#define DEFAULT_NOZEROFIXING FALSE /**< should variables with a zero shifting value be delayed instead of being fixed? */
90#define DEFAULT_FIXBINLOCKS TRUE /**< should binary variables with no locks in one direction be fixed to that direction? */
91#define DEFAULT_BINLOCKSFIRST FALSE /**< should binary variables with no locks be preferred in the ordering? */
92#define DEFAULT_NORMALIZE TRUE /**< should coefficients and left/right hand sides be normalized by max row coeff? */
93#define DEFAULT_UPDATEWEIGHTS FALSE /**< should row weight be increased every time the row is violated? */
94#define DEFAULT_IMPLISCONTINUOUS TRUE /**< should implicit integer variables be treated as continuous variables? */
95#define DEFAULT_MINFIXINGRATELP 0.0 /**< minimum fixing rate over all variables (including continuous) to solve LP */
114 SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */
117 int cutoffbreaker; /**< the number of cutoffs before heuristic execution is stopped, or -1 for no
121 SCIP_Real maxcutoffquot; /**< maximum percentage of allowed cutoffs before stopping the heuristic */
122 SCIP_Real minfixingratelp; /**< minimum fixing rate over all variables (including continuous) to solve LP */
126 SCIP_Bool stopafterfeasible; /**< Should the heuristic stop calculating optimal shift values when no
129 SCIP_Bool nozerofixing; /**< should variables with a zero shifting value be delayed instead of being fixed? */
130 SCIP_Bool fixbinlocks; /**< should binary variables with no locks in one direction be fixed to that direction? */
131 SCIP_Bool binlocksfirst; /**< should binary variables with no locks be preferred in the ordering? */
134 SCIP_Bool impliscontinuous; /**< should implicit integer variables be treated as continuous variables? */
135 SCIP_Bool selectbest; /**< should the heuristic choose the best candidate in every round? (set to FALSE for static order)? */
153};
166 TRANSFORMSTATUS* transformstatus; /**< information about transform status of every discrete variable */
170 SCIP_Real* upperbounds; /**< the upper bounds of every non-continuous variable after transformation*/
171 SCIP_Real* transformshiftvals; /**< values by which original discrete variable bounds were shifted */
197/** returns whether a given variable is counted as discrete, depending on the parameter impliscontinuous */
204 return SCIPvarIsIntegral(var) && (SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT || !impliscontinuous);
207/** returns whether a given column is counted as discrete, depending on the parameter impliscontinuous */
214 return SCIPcolIsIntegral(col) && (!impliscontinuous || SCIPvarGetType(SCIPcolGetVar(col)) != SCIP_VARTYPE_IMPLINT);
417 /* if both lower and upper bound are -infinity and infinity, resp., this is reflected by a free transform status.
418 * If the lower bound is already zero, this is reflected by identity transform status. In both cases, none of the
448 /* determine the upper bound for this variable in heuristic transformation (lower bound is implicit; always 0) */
489 SCIPdebugMsg(scip, "Variable <%s> at colpos %d transformed. Status %d LB <%g> --> <%g>, UB <%g> --> <%g>\n",
490 SCIPvarGetName(var), colpos, matrix->transformstatus[colpos], lb, 0.0, ub, matrix->upperbounds[colpos]);
493/** initializes copy of the original coefficient matrix and applies heuristic specific adjustments: normalizing row
494 * vectors, transforming variable domains such that lower bound is zero, and relaxing continuous variables.
618 /* in case of empty rows with a 0 < lhs <= 0.0 or 0.0 <= rhs < 0 we deduce the infeasibility of the problem */
619 if( nrowlpnonz == 0 && (SCIPisFeasPositive(scip, matrix->lhs[i]) || SCIPisFeasNegative(scip, matrix->rhs[i])) )
670 /* loop over all rows with nonzero coefficients in the column, transform them and add them to the heuristic matrix */
715 SCIPdebugMsg(scip, "Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n",
794 if( violatedrowpos[rowindex] == -1 && (SCIPisFeasGT(scip, matrix->lhs[rowindex], 0.0) || SCIPisFeasLT(scip, matrix->rhs[rowindex], 0.0)) )
807 else if( violatedrowpos[rowindex] >= 0 && SCIPisFeasLE(scip, matrix->lhs[rowindex], 0.0) && SCIPisFeasGE(scip, matrix->rhs[rowindex], 0.0) )
856 /* check if we requested an update for a single variable, or if we want to (re)-initialize the whole violation info */
887 checkRowViolation(scip, matrix, rowpos, violatedrows, violatedrowpos, nviolatedrows, rowweights, updateweights);
889 assert((violatedrowpos[rowpos] == -1 && SCIPisFeasGE(scip, matrix->rhs[rowpos], 0.0) && SCIPisFeasLE(scip, matrix->lhs[rowpos], 0.0))
890 || (violatedrowpos[rowpos] >= 0 &&(SCIPisFeasLT(scip, matrix->rhs[rowpos], 0.0) || SCIPisFeasGT(scip, matrix->lhs[rowpos], 0.0))));
912 /* check if original variable has different bounds and transform solution value correspondingly */
928 * @todo if there is already an incumbent solution, try considering the objective cutoff as additional constraint */
992 /* for a feasible row, determine the minimum integer value within the bounds of the variable by which it has to be
1002 * i.e. a positive coefficient for a "<="-constraint, a negative coefficient for a ">="-constraint.
1003 * if the variable has no lock in the current row, it can still help to increase the slack of this row;
1021 /* check if the least violating shift lies within variable bounds and set corresponding array values */
1022 if( !SCIPisInfinity(scip, maxfeasshift) && SCIPisFeasLE(scip, maxfeasshift + 1.0, upperbound) )
1034 /* for a violated row, determine the minimum integral value within the bounds of the variable by which it has to be
1043 /* if coefficient has the right sign to make row feasible, determine the minimum integer to shift variable
1057 /* check if the minimum feasibility recovery shift lies within variable bounds and set corresponding array
1074 /* in case that the variable cannot affect the feasibility of any row, in particular it cannot violate
1094 /* best shifting step is calculated by summing up the violation changes for each relevant step and
1095 * taking the one which leads to the minimum sum. This sum measures the balance of feasibility recovering and
1097 * note, the sums for smaller steps have to be taken into account for all bigger steps, i.e., the sums can be
1104 /* if we reached the last entry for the current step value, we have finished computing its sum and
1119/** updates transformation of a given variable by taking into account current local bounds. if the bounds have changed
1120 * since last update, updating the heuristic specific upper bound of the variable, its current transformed solution value
1148 SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1198 assert(matrix->transformstatus[varindex] == TRANSFORMSTATUS_LB || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1199 assert(SCIPisLE(scip, ABS(lb), ABS(ub)) || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1205 SCIPerrorMessage("Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n", status);
1209 /* if the bound, by which the variable was shifted, has changed, deltashift is different from zero, which requires
1222 /* go through rows, update the rows w.r.t. the influence of the changed transformation of the variable */
1239 checkViolations(scip, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1241 SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1336 " SHIFTANDPROPAGATE PROBING : %d probings, %" SCIP_LONGINT_FORMAT " domain reductions, ncutoffs: %d , LP iterations: %" SCIP_LONGINT_FORMAT " \n ",
1346/** initialization method of primal heuristic(called after problem was transformed). We only need this method for
1486 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1520 /* copy and sort the columns by their variable types (binary before integer before implicit integer before continuous) */
1527 /* we have to collect the number of different variable types before we start probing since during probing variable
1551 /* save the position of this column in the array such that it can be accessed as the "true" column position */
1566 /* this should always be fulfilled because we perform shift and propagate only at the root node */
1578 SCIP_CALL( initMatrix(scip, matrix, heurdata, colposs, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1587 /* the number of discrete LP column variables can be less than the actual number of variables, if, e.g., there
1592 SCIPdebugMsg(scip, "Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1638 checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1649 /* sort variables w.r.t. the sorting key parameter. Sorting is indirect, all matrix column data
1701 SCIPdebugMsg(scip, "Variables sorted down w.r.t their number of currently infeasible rows!\n");
1718 SCIPdebugMsg(scip, "Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1780 /* if c reaches nbinwithoutlocks, then all binary variables without locks were sorted to the beginning of the array */
1829 assert((c < nbinwithoutlocks) == (SCIPvarIsBinary(SCIPcolGetVar(heurdata->lpcols[permutation[c]]))
1830 && (SCIPvarGetNLocksUpType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0
1831 || SCIPvarGetNLocksDownType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0)));
1853 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], NULL) );
1862 SCIPdebugMsg(scip, "SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1867 /* loop over variables, shift them according to shifting criteria and try to reduce the global infeasibility */
1918 SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex,lb, ub, violatedrows, violatedrowpos,
1923 SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1938 /* check whether the variable is binary and has no locks in one direction, so that we want to fix it to the
1955 /* only apply the computationally expensive best shift selection, if there is a violated row left */
1959 SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, 1, heurdata->rowweights, steps, violationchange,
1971 SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, -1, heurdata->rowweights, steps, violationchange,
1986 /* if zero optimal shift values are forbidden by the user parameter, delay the variable by marking it suspicious */
2002 /* if propagation is enabled, fix the variable to the new solution value and propagate the fixation
2007 /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2016 SCIPdebugMsg(scip, " Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2021 SCIPdebugMsg(scip, "Propagation finished! <%" SCIP_LONGINT_FORMAT "> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ? "CUTOFF" : "",
2034 if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot * SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2043 /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2048 /* if the variable upper and lower bound are equal to the solution value to which we tried to fix the variable,
2049 * we are trapped at an infeasible node and break; this can only happen due to an intermediate global bound change of the variable,
2052 if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
2057 else if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2059 /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2060 * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2071 else if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2073 /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2074 * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2087 /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
2095 /* since repropagation was successful, we indicate that this variable led to a cutoff in one direction */
2111 SCIPdebugMsg(scip, " Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2115 SCIPdebugMsg(scip, "Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2128 SCIPdebugMsg(scip, "Heuristic finished with %d remaining violations and %d remaining variables!\n",
2131 /* if constructed solution might be feasible, go through the queue of suspicious variables and set the solution
2151 /* update the transformation of the variable, since the bound might have changed after the last update. */
2153 SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex, SCIPvarGetLbLocal(var),
2156 /* retransform the solution value from the heuristic transformed space, set the solution value accordingly */
2162 SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) ); /* only to ensure that some assertions can be made later */
2164 SCIPdebugMsg(scip, " Remaining variable <%s> set to <%g>; %d Violations\n", SCIPvarGetName(var), origsolval,
2174 /* check if enough variables have been fixed (including continuous) to solve the remaining LP */
2227 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
2237 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
2243 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2249 * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
2250 * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2258 SCIPwarningMessage(scip, "Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2266 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2282 * None of integrality, feasibility of LP rows, variable bounds have to be checked, because they
2309 SCIPstatisticMessage(" Shiftandpropagate solution value: %16.9g \n", SCIPgetSolOrigObj(scip, sol));
2330 SCIP_CALL( SCIPdropVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], -1) );
2406 SCIP_CALL( updateTransformation(scip, matrix, eventhdlrdata->heurdata, colpos, lb, ub, eventhdlrdata->violatedrows,
2457 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/relax", "Should continuous variables be relaxed?",
2459 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/probing", "Should domains be reduced by probing?",
2464 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/cutoffbreaker", "The number of cutoffs before heuristic stops",
2467 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2469 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/sortvars", "Should variables be sorted for the heuristic?",
2471 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/collectstats", "should variable statistics be collected during probing?",
2498 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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:167
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:83
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:139
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:57
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10149
SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)
Definition: heur_shiftandpropagate.c:2417
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:104
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:334
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:471
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
Definition: scip_probing.c:1045
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:418
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
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:2954
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:446
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:79
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:56
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
static void relaxVar(SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix)
Definition: heur_shiftandpropagate.c:291
static void transformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)
Definition: heur_shiftandpropagate.c:389
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:930
static void getRowData(CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)
Definition: heur_shiftandpropagate.c:219
static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
Definition: heur_shiftandpropagate.c:1249
static void checkRowViolation(SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
Definition: heur_shiftandpropagate.c:770
static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)
Definition: heur_shiftandpropagate.c:209
static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
Definition: heur_shiftandpropagate.c:1414
static SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
Definition: heur_shiftandpropagate.c:2373
static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)
Definition: heur_shiftandpropagate.c:722
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:1124
static SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
Definition: heur_shiftandpropagate.c:1318
static SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
Definition: heur_shiftandpropagate.c:1400
static SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
Definition: heur_shiftandpropagate.c:1350
static void checkViolations(SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
Definition: heur_shiftandpropagate.c:835
static SCIP_Real retransformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)
Definition: heur_shiftandpropagate.c:896
static SCIP_Bool varIsDiscrete(SCIP_VAR *var, SCIP_Bool impliscontinuous)
Definition: heur_shiftandpropagate.c:199
static void getColumnData(CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)
Definition: heur_shiftandpropagate.c:258
static SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
Definition: heur_shiftandpropagate.c:1375
static SCIP_RETCODE initMatrix(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int *colposs, int *nmaxrows, SCIP_Bool relax, SCIP_Bool *initialized, SCIP_Bool *infeasible)
Definition: heur_shiftandpropagate.c:497
#define EVENTTYPE_SHIFTANDPROPAGATE
Definition: heur_shiftandpropagate.c:99
preroot heuristic that alternatingly fixes variables and propagates domains
memory allocation routines
Definition: objbenders.h:44
public methods for managing events
public methods for primal heuristics
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for problem variables
public methods for event handler plugins and event handlers
general public methods
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 SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
Definition: struct_lp.h:136
Definition: struct_event.h:205
Definition: struct_heur.h:98
Definition: struct_misc.h:269
Definition: struct_lp.h:202
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70