SCIP
Solving Constraint Integer Programs
prop_redcost.c File Reference
Detailed Description
propagator using the LP reduced cost and the cutoff bound
This propagator uses the reduced cost of an optimal solved LP relaxation to propagate the variables against the cutoff bound.
Definition in file prop_redcost.c.
#include "lpi/type_lpi.h"#include "scip/prop_redcost.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_prop.h"#include "scip/pub_tree.h"#include "scip/pub_var.h"#include "scip/scip_branch.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_pricer.h"#include "scip/scip_prob.h"#include "scip/scip_prop.h"#include "scip/scip_solvingstats.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"#include <string.h>Go to the source code of this file.
Macros | |
Propagator properties | |
| #define | PROP_NAME "redcost" |
| #define | PROP_DESC "reduced cost strengthening propagator" |
| #define | PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP |
| #define | PROP_PRIORITY +1000000 |
| #define | PROP_FREQ 1 |
| #define | PROP_DELAY FALSE |
Default parameter values | |
| #define | DEFAULT_CONTINUOUS FALSE |
| #define | DEFAULT_USEIMPLICS FALSE |
| #define | DEFAULT_FORCE FALSE |
Functions | |
| SCIP_RETCODE | SCIPincludePropRedcost (SCIP *scip) |
Local methods | |
| static SCIP_RETCODE | propagateRootRedcostBinvar (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real cutoffbound, int *nchgbds) |
| static SCIP_RETCODE | propagateRedcostBinvar (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real requiredredcost, int *nchgbds, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateRedcostVar (SCIP *scip, SCIP_VAR *var, SCIP_COL *col, SCIP_Real lpobjval, SCIP_Real cutoffbound, int *nchgbds) |
Callback methods of propagator | |
| static | SCIP_DECL_PROPCOPY (propCopyRedcost) |
| static | SCIP_DECL_PROPFREE (propFreeRedcost) |
| static | SCIP_DECL_PROPINITSOL (propInitsolRedcost) |
| static | SCIP_DECL_PROPEXEC (propExecRedcost) |
Macro Definition Documentation
◆ PROP_NAME
| #define PROP_NAME "redcost" |
Definition at line 57 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ PROP_DESC
| #define PROP_DESC "reduced cost strengthening propagator" |
Definition at line 58 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ PROP_TIMING
| #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 59 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ PROP_PRIORITY
| #define PROP_PRIORITY +1000000 |
propagator priority
Definition at line 60 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ PROP_FREQ
| #define PROP_FREQ 1 |
propagator frequency
Definition at line 61 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ PROP_DELAY
| #define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 62 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ DEFAULT_CONTINUOUS
| #define DEFAULT_CONTINUOUS FALSE |
should reduced cost fixing be also applied to continuous variables?
Definition at line 72 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ DEFAULT_USEIMPLICS
| #define DEFAULT_USEIMPLICS FALSE |
should implications be used to strength the reduced cost for binary variables?
Definition at line 73 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
◆ DEFAULT_FORCE
| #define DEFAULT_FORCE FALSE |
should the propagator be forced even if active pricer are present? Note that the reductions are always valid, but installing an upper bound on priced variables may lead to problems in pricing (existing variables at their upper bound may be priced again since they may have negative reduced costs)
Definition at line 74 of file prop_redcost.c.
Referenced by SCIPincludePropRedcost().
Function Documentation
◆ propagateRootRedcostBinvar()
|
static |
propagate the given binary variable/column using the root reduced cost stored in the SCIP internal data structures and check if the implications can be useful. Depending on that implications are used or not used during the search to strength the reduced costs.
- Parameters
-
scip SCIP data structure propdata propagator data structure var variable to use for propagation col LP column of the variable cutoffbound the current cutoff bound nchgbds pointer to count the number of bound changes
Definition at line 111 of file prop_redcost.c.
References FALSE, MAX, NULL, propagateRedcostBinvar(), SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPchgVarLb(), SCIPchgVarUb(), SCIPcolGetBasisStatus(), SCIPdebugMsg, SCIPgetDepth(), SCIPgetVarImplRedcost(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisLPDualReliable(), SCIPvarGetBestRootLPObjval(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootSol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
◆ propagateRedcostBinvar()
|
static |
propagate the given binary variable/column using the reduced cost
- Parameters
-
scip SCIP data structure propdata propagator data structure var variable to use for propagation col LP column of the variable requiredredcost required reduset cost to be able to fix a binary variable nchgbds pointer to count the number of bound changes cutoff pointer to store if an cutoff was detected
Definition at line 235 of file prop_redcost.c.
References FALSE, propagateRedcostVar(), SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPchgVarLb(), SCIPchgVarUb(), SCIPcolGetBasisStatus(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetColRedcost(), SCIPgetVarImplRedcost(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisLPDualReliable(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateRootRedcostBinvar().
◆ propagateRedcostVar()
|
static |
propagate the given none binary variable/column using the reduced cost
- Parameters
-
scip SCIP data structure var variable to use for propagation col LP column of the variable lpobjval objective value of the current LP cutoffbound the current cutoff bound nchgbds pointer to count the number of bound changes
Definition at line 369 of file prop_redcost.c.
References NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPCOPY(), SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPadjustedVarLb(), SCIPadjustedVarUb(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPcolGetBasisStatus(), SCIPcolGetLb(), SCIPcolGetMaxPrimsol(), SCIPcolGetMinPrimsol(), SCIPcolGetUb(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetColRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasLT(), SCIPisLPDualReliable(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and SCIPvarIsIntegral().
Referenced by propagateRedcostBinvar().
◆ SCIP_DECL_PROPCOPY()
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 520 of file prop_redcost.c.
Referenced by propagateRedcostVar().
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting) ! [SnippetPropFreeRedcost]
Definition at line 535 of file prop_redcost.c.
◆ SCIP_DECL_PROPINITSOL()
|
static |
! [SnippetPropFreeRedcost] solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 553 of file prop_redcost.c.
◆ SCIP_DECL_PROPEXEC()
|
static |
reduced cost propagation method for an LP solution
Definition at line 568 of file prop_redcost.c.