Scippy

SCIP

Solving Constraint Integer Programs

redcosts.c File Reference

Detailed Description

Reduced cost based routines for Steiner problems.

Author
Daniel Rehfeldt

This file encompasses various routines for reduced costs based computations

Definition in file redcosts.c.

#include "redcosts.h"
#include "graph.h"
#include "portab.h"

Go to the source code of this file.

Data Structures

struct  reduce_costs_data
 

Functions

Local methods
static SCIP_RETCODE initFromParams (SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
 
static int getTopLevel (const REDCOST *redcostdata)
 
static SCIP_Bool levelIsValid (const REDCOST *redcostdata, int level)
 
static int getStartPositionCloseTerms (const REDCOST *redcostdata, int level)
 
Interface methods
int redcosts_getNnodes (const REDCOST *redcostdata)
 
int redcosts_getNedges (const REDCOST *redcostdata)
 
SCIP_Realredcosts_getEdgeCosts (const REDCOST *redcostdata, int level)
 
SCIP_Realredcosts_getEdgeCostsTop (const REDCOST *redcostdata)
 
SCIP_Realredcosts_getRootToNodeDist (const REDCOST *redcostdata, int level)
 
SCIP_Realredcosts_getRootToNodeDistTop (const REDCOST *redcostdata)
 
PATHredcosts_getNodeToTermsPaths (const REDCOST *redcostdata, int level)
 
PATHredcosts_getNodeToTermsPathsTop (const REDCOST *redcostdata)
 
int * redcosts_getNodeToTermsBases (const REDCOST *redcostdata, int level)
 
int * redcosts_getNodeToTermsBasesTop (const REDCOST *redcostdata)
 
SCIP_Real redcosts_getCutoff (const REDCOST *redcostdata, int level)
 
SCIP_Real redcosts_getCutoffTop (const REDCOST *redcostdata)
 
SCIP_Real redcosts_getDualBound (int level, const REDCOST *redcostdata)
 
SCIP_Real redcosts_getDualBoundTop (const REDCOST *redcostdata)
 
int redcosts_getRoot (const REDCOST *redcostdata, int level)
 
int redcosts_getRootTop (const REDCOST *redcostdata)
 
int redcosts_getLevel (const REDCOST *redcostdata)
 
int redcosts_getNlevels (const REDCOST *redcostdata)
 
void redcosts_setCutoff (SCIP_Real cutoff, int level, REDCOST *redcostdata)
 
void redcosts_setCutoffTop (SCIP_Real cutoff, REDCOST *redcostdata)
 
void redcosts_setDualBound (SCIP_Real dualbound, int level, REDCOST *redcostdata)
 
void redcosts_setDualBoundTop (SCIP_Real dualbound, REDCOST *redcostdata)
 
void redcosts_setRoot (int root, int level, REDCOST *redcostdata)
 
void redcosts_setRootTop (int root, REDCOST *redcostdata)
 
void redcosts_addLevel (REDCOST *redcostdata)
 
SCIP_RETCODE redcosts_initializeDistances (SCIP *scip, int level, GRAPH *g, REDCOST *redcostdata)
 
SCIP_RETCODE redcosts_initializeDistancesTop (SCIP *scip, GRAPH *g, REDCOST *redcostdata)
 
SCIP_RETCODE redcosts_initFromParams (SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
 
SCIP_RETCODE redcosts_init (SCIP *scip, int nnodes, int nedges, SCIP_Real cutoff, int redCostRoot, REDCOST **redcostdata)
 
void redcosts_setAndReturnCutoffFromBoundTop (SCIP_Real upperbound, REDCOST *redcostdata, SCIP_Real *cutoffbound)
 
void redcosts_setCutoffFromBound (SCIP_Real upperbound, int level, REDCOST *redcostdata)
 
void redcosts_setCutoffFromBoundTop (SCIP_Real upperbound, REDCOST *redcostdata)
 
void redcosts_increaseOnDeletedArcs (const GRAPH *graph, const STP_Bool *arcsdeleted, int level, REDCOST *redcostdata)
 
void redcosts_unifyBlockedEdgeCosts (const GRAPH *graph, int level, REDCOST *redcostdata)
 
void redcosts_increaseOnDeletedArcsTop (const GRAPH *graph, const STP_Bool *arcsdeleted, REDCOST *redcostdata)
 
void redcosts_free (SCIP *scip, REDCOST **redcostdata)
 
SCIP_Bool redcosts_forLPareAvailable (SCIP *scip)
 
SCIP_Bool redcosts_forLPareReliable (SCIP *scip, SCIP_VAR **vars, const GRAPH *graph)
 
void redcosts_forLPget (SCIP *scip, SCIP_VAR **vars, const GRAPH *graph, SCIP_Real *redcosts)
 

Function Documentation

◆ initFromParams()

◆ getTopLevel()

◆ levelIsValid()

static SCIP_Bool levelIsValid ( const REDCOST redcostdata,
int  level 
)
static

◆ getStartPositionCloseTerms()

static int getStartPositionCloseTerms ( const REDCOST redcostdata,
int  level 
)
static

returns start position of given level for lvl_nodeToTermsPaths and lvl_nodeToTermsBases

Parameters
redcostdatareduced costs data
levelthe level

Definition at line 140 of file redcosts.c.

References levelIsValid(), reduce_costs_data::nCloseTerms, and reduce_costs_data::nnodes.

Referenced by redcosts_getNodeToTermsBases(), and redcosts_getNodeToTermsPaths().

◆ redcosts_getNnodes()

int redcosts_getNnodes ( const REDCOST redcostdata)

returns number of nodes for which reduced costs are stored

Parameters
redcostdatareduced costs data

Definition at line 165 of file redcosts.c.

References reduce_costs_data::nnodes.

Referenced by extInitRedCostArrays(), and extreduce_redcostAddEdge().

◆ redcosts_getNedges()

int redcosts_getNedges ( const REDCOST redcostdata)

returns number of edges for which reduced costs are stored

Parameters
redcostdatareduced costs data

Definition at line 176 of file redcosts.c.

References reduce_costs_data::nedges.

Referenced by extInitRedCostArrays(), extreduce_redcostAddEdge(), extreduce_redcostRemoveEdge(), and extreduce_redcostTreeRecompute().

◆ redcosts_getEdgeCosts()

◆ redcosts_getEdgeCostsTop()

◆ redcosts_getRootToNodeDist()

SCIP_Real* redcosts_getRootToNodeDist ( const REDCOST redcostdata,
int  level 
)

returns root to node distances

Parameters
redcostdatareduced costs data
levellevel to get distances for

Definition at line 213 of file redcosts.c.

References levelIsValid(), reduce_costs_data::lvl_rootToNodeDist, and reduce_costs_data::nnodes.

Referenced by extTreeGetDirectedRedcostProper(), getTreeRedcosts_dbg(), redcosts_getRootToNodeDistTop(), and redcosts_initializeDistances().

◆ redcosts_getRootToNodeDistTop()

SCIP_Real* redcosts_getRootToNodeDistTop ( const REDCOST redcostdata)

◆ redcosts_getNodeToTermsPaths()

PATH* redcosts_getNodeToTermsPaths ( const REDCOST redcostdata,
int  level 
)

returns paths from nodes to closes terms

Parameters
redcostdatareduced costs data
levellevel to get reduced costs for

Definition at line 240 of file redcosts.c.

References getStartPositionCloseTerms(), and reduce_costs_data::lvl_nodeToTermsPaths.

Referenced by extTreeGetDirectedRedcostProper(), getTreeRedcosts_dbg(), redcosts_getNodeToTermsPathsTop(), and redcosts_initializeDistances().

◆ redcosts_getNodeToTermsPathsTop()

PATH* redcosts_getNodeToTermsPathsTop ( const REDCOST redcostdata)

◆ redcosts_getNodeToTermsBases()

int* redcosts_getNodeToTermsBases ( const REDCOST redcostdata,
int  level 
)

returns closest terminals to nodes

Parameters
redcostdatareduced costs data
levellevel to terminals for

Definition at line 264 of file redcosts.c.

References getStartPositionCloseTerms(), and reduce_costs_data::lvl_nodeToTermsBases.

Referenced by extTreeGetDirectedRedcostProper(), redcosts_getNodeToTermsBasesTop(), and redcosts_initializeDistances().

◆ redcosts_getNodeToTermsBasesTop()

int* redcosts_getNodeToTermsBasesTop ( const REDCOST redcostdata)

returns closest terms to nodes for top level

Parameters
redcostdatareduced costs data

Definition at line 277 of file redcosts.c.

References getTopLevel(), redcosts_getNodeToTermsBases(), and reduce_costs_data::toplevel.

Referenced by extInitRedCostArrays(), extInitRedCostArraysPc(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletion3_deprecated(), and updateNodeReplaceBounds().

◆ redcosts_getCutoff()

SCIP_Real redcosts_getCutoff ( const REDCOST redcostdata,
int  level 
)

returns cutoff

Parameters
redcostdatareduced costs data
levellevel to get cutoff for

Definition at line 288 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_cutoff.

Referenced by extTreeRedcostCutoff(), fixVarsExtendedRed(), fixVarsRedbased(), redcosts_getCutoffTop(), redcosts_increaseOnDeletedArcs(), redcosts_unifyBlockedEdgeCosts(), and reduceWithEdgeExtReds().

◆ redcosts_getCutoffTop()

◆ redcosts_getDualBound()

SCIP_Real redcosts_getDualBound ( int  level,
const REDCOST redcostdata 
)

returns dual-bound

Parameters
levellevel
redcostdatareduced costs data

Definition at line 311 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_dualBound.

Referenced by redcosts_getDualBoundTop(), and redcosts_setCutoffFromBound().

◆ redcosts_getDualBoundTop()

SCIP_Real redcosts_getDualBoundTop ( const REDCOST redcostdata)

returns dual-bound for top level

Parameters
redcostdatareduced costs data

Definition at line 324 of file redcosts.c.

References getTopLevel(), redcosts_getDualBound(), and reduce_costs_data::toplevel.

Referenced by redcosts_setAndReturnCutoffFromBoundTop(), reduce_da(), and updateNodeReplaceBounds().

◆ redcosts_getRoot()

int redcosts_getRoot ( const REDCOST redcostdata,
int  level 
)

returns root used for reduced cost computation

Parameters
redcostdatareduced costs data
levellevel to get root for

Definition at line 335 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_redCostRoot.

Referenced by extreduce_redcostInitExpansion(), redcosts_getRootTop(), and redcosts_initializeDistances().

◆ redcosts_getRootTop()

int redcosts_getRootTop ( const REDCOST redcostdata)

◆ redcosts_getLevel()

int redcosts_getLevel ( const REDCOST redcostdata)

returns current (top) level; 0-indexed

Parameters
redcostdatareduced costs data

Definition at line 358 of file redcosts.c.

References getTopLevel(), and reduce_costs_data::toplevel.

Referenced by updateRedcostdata().

◆ redcosts_getNlevels()

int redcosts_getNlevels ( const REDCOST redcostdata)

returns current number of levels

Parameters
redcostdatareduced costs data

Definition at line 369 of file redcosts.c.

References getTopLevel(), and reduce_costs_data::toplevel.

Referenced by delPseudoDeleteVertex(), delPseudoInit(), extreduce_checkComponent(), fixVarsExtendedRed(), fixVarsRedbased(), reduceWithEdgeExtReds(), and updateRedcostdata().

◆ redcosts_setCutoff()

void redcosts_setCutoff ( SCIP_Real  cutoff,
int  level,
REDCOST redcostdata 
)

sets cutoff

Parameters
cutoffthe value
levellevel to set cutoff for
redcostdatareduced costs data

Definition at line 380 of file redcosts.c.

References GE, levelIsValid(), and reduce_costs_data::lvl_cutoff.

Referenced by redcosts_setCutoffFromBound(), redcosts_setCutoffTop(), and writeRedcostdata().

◆ redcosts_setCutoffTop()

void redcosts_setCutoffTop ( SCIP_Real  cutoff,
REDCOST redcostdata 
)

sets cutoff for top level

Parameters
cutoffthe value
redcostdatareduced costs data

Definition at line 394 of file redcosts.c.

References getTopLevel(), redcosts_setCutoff(), and reduce_costs_data::toplevel.

Referenced by redcosts_setAndReturnCutoffFromBoundTop(), and testEdgeDeletedByMultiRedCosts().

◆ redcosts_setDualBound()

void redcosts_setDualBound ( SCIP_Real  dualbound,
int  level,
REDCOST redcostdata 
)

sets dual-bound

Parameters
dualboundthe value
levellevel to set dual bound for
redcostdatareduced costs data

Definition at line 406 of file redcosts.c.

References GE, levelIsValid(), and reduce_costs_data::lvl_dualBound.

Referenced by redcosts_setDualBoundTop(), and writeRedcostdata().

◆ redcosts_setDualBoundTop()

void redcosts_setDualBoundTop ( SCIP_Real  dualbound,
REDCOST redcostdata 
)

sets dual-bound

Parameters
dualboundthe value
redcostdatareduced costs data

Definition at line 420 of file redcosts.c.

References GE, getTopLevel(), redcosts_setDualBound(), and reduce_costs_data::toplevel.

Referenced by computeDualSolution(), computeDualSolutionGuided(), reduce_dapaths(), and termcompReduceWithParams().

◆ redcosts_setRoot()

void redcosts_setRoot ( int  root,
int  level,
REDCOST redcostdata 
)

sets root used for reduced cost computation

Parameters
rootthe root
levellevel to set dual bound for
redcostdatareduced costs data

Definition at line 433 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_redCostRoot.

Referenced by redcosts_setRootTop(), and writeRedcostdata().

◆ redcosts_setRootTop()

void redcosts_setRootTop ( int  root,
REDCOST redcostdata 
)

sets root used for reduced cost computation

Parameters
rootthe root
redcostdatareduced costs data

Definition at line 447 of file redcosts.c.

References getTopLevel(), redcosts_setRoot(), and reduce_costs_data::toplevel.

Referenced by reduce_da(), and testEdgeDeletedByMultiRedCosts().

◆ redcosts_addLevel()

void redcosts_addLevel ( REDCOST redcostdata)

adds a new level

Parameters
redcostdatareduced costs data

Definition at line 460 of file redcosts.c.

References reduce_costs_data::nLevelsMax, and reduce_costs_data::toplevel.

Referenced by reduce_da(), testEdgeDeletedByMultiRedCosts(), and updateRedcostdata().

◆ redcosts_initializeDistances()

◆ redcosts_initializeDistancesTop()

SCIP_RETCODE redcosts_initializeDistancesTop ( SCIP scip,
GRAPH g,
REDCOST redcostdata 
)
Parameters
scipSCIP
ggraph data structure
redcostdatareduced cost data

Definition at line 573 of file redcosts.c.

References getTopLevel(), redcosts_initializeDistances(), SCIP_CALL, SCIP_OKAY, and reduce_costs_data::toplevel.

Referenced by daRoundInit(), reduce_dapaths(), termcompReduceWithParams(), and testEdgeDeletedByMultiRedCosts().

◆ redcosts_initFromParams()

SCIP_RETCODE redcosts_initFromParams ( SCIP scip,
const RCPARAMS parameters,
REDCOST **  redcostdata 
)

initializes reduced costs data structure from given parameter struct

Parameters
scipSCIP
parametersparameters for initialization
redcostdatadata to initialize

Definition at line 590 of file redcosts.c.

References initFromParams(), SCIP_CALL, and SCIP_OKAY.

Referenced by daRedcostsInit(), initRedcostdata(), redcosts_init(), termcompReduceWithParams(), and testEdgeDeletedByMultiRedCosts().

◆ redcosts_init()

SCIP_RETCODE redcosts_init ( SCIP scip,
int  nnodes,
int  nedges,
SCIP_Real  cutoff,
int  redCostRoot,
REDCOST **  redcostdata 
)

◆ redcosts_setAndReturnCutoffFromBoundTop()

void redcosts_setAndReturnCutoffFromBoundTop ( SCIP_Real  upperbound,
REDCOST redcostdata,
SCIP_Real cutoffbound 
)

sets cutoff

Parameters
upperboundbound
redcostdatareduced cost data
cutoffboundcutoff

Definition at line 624 of file redcosts.c.

References EPSILON, GE, GE_FEAS_EPS, redcosts_getDualBoundTop(), and redcosts_setCutoffTop().

Referenced by daRoundInit().

◆ redcosts_setCutoffFromBound()

void redcosts_setCutoffFromBound ( SCIP_Real  upperbound,
int  level,
REDCOST redcostdata 
)

sets cutoff

Parameters
upperboundbound
levellevel
redcostdatareduced cost data

Definition at line 645 of file redcosts.c.

References EPSILON, GE, GE_FEAS_EPS, levelIsValid(), redcosts_getDualBound(), redcosts_setCutoff(), and SCIP_Real.

Referenced by fixVarsExtendedRed(), fixVarsRedbased(), redcosts_setCutoffFromBoundTop(), and reduceWithEdgeExtReds().

◆ redcosts_setCutoffFromBoundTop()

void redcosts_setCutoffFromBoundTop ( SCIP_Real  upperbound,
REDCOST redcostdata 
)

sets cutoff for top level

Parameters
upperboundbound
redcostdatareduced cost data

Definition at line 670 of file redcosts.c.

References getTopLevel(), redcosts_setCutoffFromBound(), and reduce_costs_data::toplevel.

Referenced by reduce_dapaths(), and termcompReduceWithParams().

◆ redcosts_increaseOnDeletedArcs()

void redcosts_increaseOnDeletedArcs ( const GRAPH graph,
const STP_Bool arcsdeleted,
int  level,
REDCOST redcostdata 
)

increases reduced cost for deleted arcs

Parameters
graphgraph
arcsdeletedarray to mark deleted arcs
levelthe level
redcostdatareduced cost data

Definition at line 682 of file redcosts.c.

References GE, graph_get_nEdges(), reduce_costs_data::nedges, redcosts_getCutoff(), redcosts_getEdgeCosts(), and SCIP_Real.

Referenced by fixVarsExtendedRed(), and redcosts_increaseOnDeletedArcsTop().

◆ redcosts_unifyBlockedEdgeCosts()

void redcosts_unifyBlockedEdgeCosts ( const GRAPH graph,
int  level,
REDCOST redcostdata 
)

unifies costs

Parameters
graphgraph
levelthe level
redcostdatareduced cost data

Definition at line 705 of file redcosts.c.

References bound, FARAWAY, GE, graph_get_nEdges(), LT, reduce_costs_data::nedges, redcosts_getCutoff(), redcosts_getEdgeCosts(), and SCIP_Real.

Referenced by fixVarsExtendedRed(), and fixVarsRedbased().

◆ redcosts_increaseOnDeletedArcsTop()

void redcosts_increaseOnDeletedArcsTop ( const GRAPH graph,
const STP_Bool arcsdeleted,
REDCOST redcostdata 
)

increases reduced cost for deleted arcs for top level

Parameters
graphgraph
arcsdeletedarray to mark deleted arcs
redcostdatareduced cost data

Definition at line 728 of file redcosts.c.

References getTopLevel(), redcosts_increaseOnDeletedArcs(), and reduce_costs_data::toplevel.

Referenced by reduce_da().

◆ redcosts_free()

◆ redcosts_forLPareAvailable()

SCIP_Bool redcosts_forLPareAvailable ( SCIP scip)

reduced costs available?

Parameters
scipSCIP structure

Definition at line 767 of file redcosts.c.

References FALSE, SCIP_LPSOLSTAT_OPTIMAL, SCIPdebugMessage, SCIPgetCutoffbound(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisInfinity(), SCIPisLPRelax(), SCIPisLPSolBasic(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_PROPEXEC().

◆ redcosts_forLPareReliable()

SCIP_Bool redcosts_forLPareReliable ( SCIP scip,
SCIP_VAR **  vars,
const GRAPH graph 
)

are reduced costs reliable?

Parameters
scipSCIP structure
varsvariables (in)
graphgraph data

Definition at line 814 of file redcosts.c.

References FALSE, graph_get_nEdges(), reduce_costs_data::nedges, NULL, SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and TRUE.

Referenced by fixVarsDualcost().

◆ redcosts_forLPget()