prop_rootredcost.c
Go to the documentation of this file.
22 * This propagator uses the root reduced cost to (globally) propagate against the cutoff bound. The propagator checks if
23 * the variables with non-zero root reduced cost can exceed the cutoff bound. If this is the case the corresponding
26 * The propagate is performed during the search any time a new cutoff bound (primal solution) is found.
28 * @todo do not sort the variables; just store the cutoff bound which leads to a fixing. If that appears loop over all
30 * @todo resolve the root LP in case of repropagation and update root reduced costs use root LP counter to check if new
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 #define PROP_DESC "reduced cost strengthening using root node reduced costs and the cutoff bound"
66 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
75 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
91 SCIP_Real lastcutoffbound; /**< cutoff bound for which the root reduced costs were already processed */
111 {
159 )
201 )
224 )
247 SCIPdebugMsg(scip, "There are %d (poor) binary variables with non-zero root reduced cost <%s>.\n", nredcostbinvars, SCIPgetProbName(scip));
262 SCIPdebugMsg(scip, "Store non-zero root reduced cost variables at address <%p>.\n", (void*)propdata->redcostvars);
300 /* sort binary variables with respect to their cutoff bound which would lead to an fixing; this order can be used
307 SCIPdebugMsg(scip, "variables with non-zero redcostective coefficient: %d binaries, %d non-binaries\n", nredcostbinvars, nredcostvars - nredcostbinvars);
337 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
338 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
339 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
352 assert(SCIPisFeasLE(scip, rootsol, SCIPvarGetLbGlobal(var))); /* lb might have been increased in the meantime */
360 assert(SCIPisFeasGE(scip, rootsol, SCIPvarGetUbGlobal(var))); /* ub might have been decreased in the meantime */
384 /* the binary variables are stored in the beginning of the variable array; these variables are sorted w.r.t. cutoff
393 * @note In case the assertion fails it indicates that a new LP root solving arose after we initialized the
394 * propagator; The new LP solution destroyed the sorting of the binary variables since the reduced cost of the
395 * variables changed. This could lead to potentially missing a domain reductions. Currently, it is not possible to
396 * check if a new root LP was solved, changing the root reduced costs. This case, however, should not happen in the
423 /* check if the variables is already globally fixed; if so continue with the next potential candidate */
432 /* @note The variable might not be globally fixed right away since this would destroy the local internal data
433 * structure of a search node; the bound change is in that case pending; hence we cannot assert that the
438 SCIPdebugMsg(scip, "globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n",
448 /* The binary variables are sorted in non-increasing manner w.r.t. their cutoff bound which would lead to a
449 * global fixing; That is, abs(rootredcost) + rootlpobjval. Depending on the sign of the reduced cost the
452 * - redcost > 0 --> newub = 0.0 + (cutoffbound - lpobjval) / redcost --> newub = 0 <=> cutoffbound < redcost + lpobjval = sorting key
453 * - redcost < 0 --> newlb = 1.0 + (cutoffbound - lpobjval) / redcost --> newlb = 1 <=> cutoffbound < -redcost + lpobjval = sorting key
455 * Due to the order of the binary variables it follows if one binary variable cannot be fixed anymore all the
456 * remaining once can also not be fixed since these have only an smaller or equal cutoff bound which would lead
459 * Note that variables with non-zero reduced cost are sitting at one of their bound. That is the lower one if
460 * the reduced cost are positive and the upper bound if the reduced cost are negative. For binary variables
463 SCIPdebugMsg(scip, "interrupt propagation for binary variables after %d from %d binary variables\n",
468 SCIPdebugMsg(scip, "detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n",
479 #if 0 /* due to numerics it might be that the abort criteria did not work correctly, because the sorting mechanism may
480 * have evaluated variables with a really small difference in their reduced cost values but with really huge
484 /* check that the abort criteria works; that means none of the remaining binary variables can be fixed */
493 /* check if the variables is already globally fixed; if so continue with the potential candidate */
547 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
585 /* the propagator should run in all nodes except the root node; for the root node the redcost propagator does
615 /* reduced cost strengthening can only be applied, if we have a finite upper bound on the LP value */
634 /* store cutoff bound to remember later that for that particular cutoff bound the propagation was already
672 /* we are done with solving since the cutoff is w.r.t. a global bound change; cutoff root node */
695 {
703 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
Definition: type_result.h:33
SCIP_EXPORT SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13578
public methods for SCIP parameter handling
Definition: struct_scip.h:59
public methods for memory management
static SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
Definition: prop_rootredcost.c:552
static int countNonZeroRootRedcostVars(SCIP *scip, SCIP_VAR **vars, int nvars)
Definition: prop_rootredcost.c:173
reduced cost strengthening using root node reduced costs and the cutoff bound
Definition: struct_var.h:198
static SCIP_RETCODE propdataInit(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_rootredcost.c:224
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
public methods for problem variables
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
SCIP_EXPORT SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition: var.c:13478
public methods for SCIP variables
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1035
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
public methods for numerical tolerances
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1011
public methods for querying solving statistics
public methods for the branch-and-bound tree
Definition: type_result.h:35
SCIP_EXPORT void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
SCIP_RETCODE SCIPincludePropRootredcost(SCIP *scip)
Definition: prop_rootredcost.c:695
Definition: type_retcode.h:33
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_rootredcost.c:201
Definition: type_result.h:42
static SCIP_RETCODE propagateBinaryBestRootRedcost(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, int *nchgbds, SCIP_Bool *cutoff)
Definition: prop_rootredcost.c:374
Definition: struct_prop.h:37
static SCIP_RETCODE propagateRootRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: prop_rootredcost.c:324
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1023
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
public methods for the LP relaxation, rows and columns
public methods for variable pricer plugins
methods for sorting joint arrays of various types
general public methods
public methods for the probing mode
public methods for message output
public methods for message handling
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6329
public methods for propagator plugins
Definition: type_set.h:44
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
static SCIP_RETCODE propdataCreate(SCIP *scip, SCIP_PROPDATA **propdata)
Definition: prop_rootredcost.c:159
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
Definition: objbenders.h:33
public methods for global and local (sub)problems
SCIP_EXPORT SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13544
Definition: type_result.h:39
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6209
public methods for propagators