Detailed Description

propagator using the LP reduced cost and the cutoff bound

Author: Tobias Achterberg; Stefan Heinz; Matthias Miltenberger; Michael Winkler

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_exact.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 67 of file prop_redcost.c.

◆ PROP_DESC

#define PROP_DESC "reduced cost strengthening propagator"

Definition at line 68 of file prop_redcost.c.

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 69 of file prop_redcost.c.

◆ PROP_PRIORITY

#define PROP_PRIORITY +1000000

propagator priority

Definition at line 70 of file prop_redcost.c.

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 71 of file prop_redcost.c.

◆ PROP_DELAY

#define PROP_DELAY FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 72 of file prop_redcost.c.

◆ DEFAULT_CONTINUOUS

#define DEFAULT_CONTINUOUS FALSE

should reduced cost fixing be also applied to continuous variables?

Definition at line 82 of file prop_redcost.c.

◆ DEFAULT_USEIMPLICS

#define DEFAULT_USEIMPLICS FALSE

should implications be used to strength the reduced cost for binary variables?

Definition at line 83 of file prop_redcost.c.

◆ 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 87 of file prop_redcost.c.

Function Documentation

◆ propagateRootRedcostBinvar()

static SCIP_RETCODE propagateRootRedcostBinvar	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var,
		SCIP_COL *	col,
		SCIP_Real	cutoffbound,
		int *	nchgbds
	)

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 118 of file prop_redcost.c.

References FALSE, MAX, NULL, 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.

Referenced by SCIP_DECL_PROPEXEC().

◆ propagateRedcostBinvar()

static SCIP_RETCODE propagateRedcostBinvar	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var,
		SCIP_COL *	col,
		SCIP_Real	requiredredcost,
		int *	nchgbds,
		SCIP_Bool *	cutoff
	)

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 242 of file prop_redcost.c.

References FALSE, MAX3, 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 SCIP_DECL_PROPEXEC().

◆ propagateRedcostVar()

static SCIP_RETCODE propagateRedcostVar	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_COL *	col,
		SCIP_Real	lpobjval,
		SCIP_Real	cutoffbound,
		int *	nchgbds
	)

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 376 of file prop_redcost.c.

References SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, 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 SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyRedcost )

static

copy method for propagator plugins (called when SCIP copies plugins)

Definition at line 527 of file prop_redcost.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropRedcost(), and SCIPpropGetName().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeRedcost )

static

destructor of propagator to free user data (called when SCIP is exiting) ! [SnippetPropFreeRedcost]

Definition at line 542 of file prop_redcost.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolRedcost )

static

! [SnippetPropFreeRedcost] solving process initialization method of propagator (called when branch and bound process is about to begin)

Definition at line 560 of file prop_redcost.c.

References FALSE, NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecRedcost )

static

reduced cost propagation method for an LP solution

Definition at line 575 of file prop_redcost.c.

References FALSE, NULL, propagateRedcostBinvar(), propagateRedcostVar(), propagateRootRedcostBinvar(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPallowWeakDualReds(), SCIPcolGetVar(), SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPCols(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNLPCols(), SCIPgetNObjVars(), SCIPgetNPseudoBranchCands(), SCIPgetNVars(), SCIPgetStage(), SCIPhasCurrentNodeLP(), SCIPisExact(), SCIPisInfinity(), SCIPisLPRelax(), SCIPisLPSolBasic(), SCIPnodeGetNumber(), SCIPpropGetData(), SCIPvarIsBinary(), and SCIPvarIsIntegral().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ DEFAULT_CONTINUOUS

◆ DEFAULT_USEIMPLICS

◆ DEFAULT_FORCE

Function Documentation

◆ propagateRootRedcostBinvar()

◆ propagateRedcostBinvar()

◆ propagateRedcostVar()

◆ SCIP_DECL_PROPCOPY()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPEXEC()