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 */
691 {
699 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
Definition: type_result.h:33
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
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
static SCIP_RETCODE propdataInit(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_rootredcost.c:224
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1011
public methods for problem variables
public methods for SCIP variables
public methods for numerical tolerances
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13815
Definition: type_result.h:35
SCIP_RETCODE SCIPincludePropRootredcost(SCIP *scip)
Definition: prop_rootredcost.c:691
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6225
Definition: type_retcode.h:33
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_rootredcost.c:201
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
Definition: type_result.h:42
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1035
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_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
public methods for the LP relaxation, rows and columns
public methods for variable pricer plugins
methods for sorting joint arrays of various types
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1023
general public methods
public methods for the probing mode
public methods for message output
public methods for message handling
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
public methods for propagator plugins
Definition: type_set.h:44
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6345
static SCIP_RETCODE propdataCreate(SCIP *scip, SCIP_PROPDATA **propdata)
Definition: prop_rootredcost.c:159
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
public methods for global and local (sub)problems
Definition: type_result.h:39
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
public methods for propagators
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