Scippy

SCIP

Solving Constraint Integer Programs

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

Referenced by SCIPincludePropRedcost().

◆ PROP_DESC

#define PROP_DESC   "reduced cost strengthening propagator"

Definition at line 67 of file prop_redcost.c.

Referenced by SCIPincludePropRedcost().

◆ PROP_TIMING

Definition at line 68 of file prop_redcost.c.

Referenced by SCIPincludePropRedcost().

◆ PROP_PRIORITY

#define PROP_PRIORITY   +1000000

propagator priority

Definition at line 69 of file prop_redcost.c.

Referenced by SCIPincludePropRedcost().

◆ PROP_FREQ

#define PROP_FREQ   1

propagator frequency

Definition at line 70 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 71 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 81 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 82 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 83 of file prop_redcost.c.

Referenced by SCIPincludePropRedcost().

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
scipSCIP data structure
propdatapropagator data structure
varvariable to use for propagation
colLP column of the variable
cutoffboundthe current cutoff bound
nchgbdspointer to count the number of bound changes

Definition at line 120 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 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
scipSCIP data structure
propdatapropagator data structure
varvariable to use for propagation
colLP column of the variable
requiredredcostrequired reduset cost to be able to fix a binary variable
nchgbdspointer to count the number of bound changes
cutoffpointer to store if an cutoff was detected

Definition at line 244 of file prop_redcost.c.

References FALSE, MAX3, 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 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
scipSCIP data structure
varvariable to use for propagation
colLP column of the variable
lpobjvalobjective value of the current LP
cutoffboundthe current cutoff bound
nchgbdspointer to count the number of bound changes

Definition at line 378 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 SCIP_DECL_PROPCOPY ( propCopyRedcost  )
static

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

Definition at line 529 of file prop_redcost.c.

Referenced by propagateRedcostVar().

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

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

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecRedcost  )
static

reduced cost propagation method for an LP solution

Definition at line 577 of file prop_redcost.c.