prop_redcost.c
Go to the documentation of this file.
33 * This propagator uses the reduced cost of an optimal solved LP relaxation to propagate the variables against the
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
71 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
81 #define DEFAULT_CONTINUOUS FALSE /**< should reduced cost fixing be also applied to continuous variables? */
82 #define DEFAULT_USEIMPLICS FALSE /**< should implications be used to strength the reduced cost for binary variables? */
83 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
99 SCIP_Bool continuous; /**< should reduced cost fixing be also applied to continuous variables? */
102 SCIP_Bool useimplics; /**< should implications be used to strength the reduced cost for binary variables? */
112 /** propagate the given binary variable/column using the root reduced cost stored in the SCIP internal data structures
113 * and check if the implications can be useful. Depending on that implications are used or not used during the search to
148 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
149 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
150 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
169 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
170 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
171 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
189 /* evaluate if the implications are useful; the implications are seen to be useful if they provide an increase for
208 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
209 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
210 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
219 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
220 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
221 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
265 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
266 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
267 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
286 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
287 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
288 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
308 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
309 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
310 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
321 /* second, if the implications should be used and if the implications are seen to be promising use the implied
329 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
330 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
331 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
344 SCIPdebugMsg(scip, "variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
351 SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
359 SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
391 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
392 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
393 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
433 SCIPdebugMsg(scip, "redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
448 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
449 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
450 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
491 SCIPdebugMsg(scip, "redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
501 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
502 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
503 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
557 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
645 /* check if all integral variables are fixed and the continuous variables should not be propagated */
655 /* skip the propagator if the problem has only binary variables and those should not be propagated */
666 SCIPdebugMsg(scip, "lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
690 SCIP_CALL( propagateRedcostBinvar(scip, propdata, var, cols[c], requiredredcost, &nchgbds, &cutoff) );
724 {
732 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
Definition: type_result.h:42
static SCIP_RETCODE propagateRedcostBinvar(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real requiredredcost, int *nchgbds, SCIP_Bool *cutoff)
Definition: prop_redcost.c:244
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
public methods for SCIP parameter handling
public methods for branch and bound tree
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
Definition: struct_scip.h:68
public methods for memory management
Definition: struct_var.h:207
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4645
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1018
public methods for problem variables
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4613
static SCIP_RETCODE propagateRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_COL *col, SCIP_Real lpobjval, SCIP_Real cutoffbound, int *nchgbds)
Definition: prop_redcost.c:378
public methods for SCIP variables
public methods for numerical tolerances
Definition: struct_lp.h:135
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13828
Definition: type_result.h:44
propagator using the LP reduced cost and the cutoff bound
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
type definitions for specific LP solvers interface
Definition: type_retcode.h:42
Definition: type_result.h:51
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1042
Definition: type_lp.h:43
Definition: struct_prop.h:46
public methods for LP management
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
public methods for the LP relaxation, rows and columns
public methods for variable pricer plugins
public methods for branching rule plugins and branching
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1030
general public methods
SCIP_Real SCIPgetVarImplRedcost(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing)
Definition: scip_var.c:1909
static SCIP_RETCODE propagateRootRedcostBinvar(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real cutoffbound, int *nchgbds)
Definition: prop_redcost.c:120
public methods for message output
Definition: type_lpi.h:91
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:215
public methods for message handling
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
public methods for propagator plugins
Definition: type_set.h:53
Definition: type_lpi.h:92
Definition: type_retcode.h:52
Definition: objbenders.h:43
public methods for global and local (sub)problems
Definition: type_lpi.h:94
Definition: type_lpi.h:93
Definition: type_result.h:48
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
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:114