Scippy

SCIP

Solving Constraint Integer Programs

prop_stp.c File Reference

Detailed Description

propagator for Steiner tree problems, using the LP reduced costs

Author
Daniel Rehfeldt

This propagator makes use of the reduced cost of an optimally solved LP relaxation to propagate the variables

Definition in file prop_stp.c.

#include <assert.h>
#include <string.h>
#include "prop_stp.h"
#include "grph.h"
#include "branch_stp.h"
#include "scip/tree.h"

Go to the source code of this file.

Macros

Propagator properties
#define PROP_NAME   "stp"
 
#define PROP_DESC   "stp propagator"
 
#define PROP_TIMING   SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
 
#define PROP_PRIORITY   1000000
 
#define PROP_FREQ   1
 
#define PROP_DELAY   FALSE
 
#define PROP_STP_EDGE_KILLED   -1
 
#define PROP_STP_EDGE_UNSET   0
 
#define PROP_STP_EDGE_SET   1
 
#define PROP_STP_EDGE_FIXED   2
 
Default parameter values
#define DEFAULT_MAXNWAITINGROUNDS   2
 
#define REDUCTION_WAIT_RATIO   0.02
 

Functions

Local methods
static SCIP_RETCODE globalfixing (SCIP *scip, SCIP_VAR **vars, int *nfixededges, const SCIP_Real *fixingbounds, const GRAPH *graph, SCIP_Real cutoffbound, int nedges)
 
static SCIP_Bool redcostAvailable (SCIP *scip)
 
static void setRedcosts (SCIP *scip, SCIP_VAR **vars, int nedges, SCIP_Real *cost)
 
static void setVnoiDistances (SCIP *scip, const SCIP_Real *cost, const GRAPH *graph, PATH *vnoi, SCIP_Real *costrev, SCIP_Real *pathdist, int *pathedge, int *vbase)
 
static void updateFixingBounds (SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjal)
 
static SCIP_RETCODE dualcostVarfixing (SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, SCIP_PROPDATA *propdata, int *nfixed, const GRAPH *graph)
 
static SCIP_RETCODE reduceRedcostExtended (SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, GRAPH *propgraph)
 
static SCIP_RETCODE redbasedVarfixing (SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, SCIP_PROPDATA *propdata, int *nfixed, SCIP_Bool *probisinfeas, const GRAPH *g)
 
Callback methods of propagator
static SCIP_DECL_PROPCOPY (propCopyStp)
 
static SCIP_DECL_PROPFREE (propFreeStp)
 
static SCIP_DECL_PROPEXEC (propExecStp)
 
static SCIP_DECL_PROPINITSOL (propInitsolStp)
 
static SCIP_DECL_PROPEXITSOL (propExitsolStp)
 
Interface methods
SCIP_RETCODE fixedgevar (SCIP *scip, SCIP_VAR *edgevar, int *nfixed)
 
int SCIPStpNfixedEdges (SCIP *scip)
 
void SCIPStpPropGetGraph (SCIP *scip, GRAPH **graph, SCIP_Longint *graphnodenumber)
 
SCIP_RETCODE SCIPincludePropStp (SCIP *scip)
 

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME   "stp"

Definition at line 39 of file prop_stp.c.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludePropStp().

◆ PROP_DESC

#define PROP_DESC   "stp propagator"

Definition at line 40 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_TIMING

Definition at line 41 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_PRIORITY

#define PROP_PRIORITY   1000000

propagator priority

Definition at line 42 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_FREQ

#define PROP_FREQ   1

propagator frequency

Definition at line 43 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_DELAY

#define PROP_DELAY   FALSE

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

Definition at line 44 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_STP_EDGE_KILLED

#define PROP_STP_EDGE_KILLED   -1

Definition at line 46 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ PROP_STP_EDGE_UNSET

#define PROP_STP_EDGE_UNSET   0

Definition at line 47 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ PROP_STP_EDGE_SET

#define PROP_STP_EDGE_SET   1

Definition at line 48 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ PROP_STP_EDGE_FIXED

#define PROP_STP_EDGE_FIXED   2

Definition at line 49 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ DEFAULT_MAXNWAITINGROUNDS

#define DEFAULT_MAXNWAITINGROUNDS   2

maximum number of rounds to wait until propagating again

Definition at line 58 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ REDUCTION_WAIT_RATIO

#define REDUCTION_WAIT_RATIO   0.02

ratio of edges to be newly fixed before performing reductions for additional fixing

Definition at line 59 of file prop_stp.c.

Referenced by SCIP_DECL_PROPEXEC().

Function Documentation

◆ globalfixing()

static SCIP_RETCODE globalfixing ( SCIP scip,
SCIP_VAR **  vars,
int *  nfixededges,
const SCIP_Real fixingbounds,
const GRAPH graph,
SCIP_Real  cutoffbound,
int  nedges 
)
static

try to make global fixings

Parameters
scipSCIP structure
varsvariables
nfixededgespoints to number of fixed edges
fixingboundsfixing bounds
graphgraph structure
cutoffboundcutoff bound
nedgesnumber of edges

Definition at line 121 of file prop_stp.c.

References SCIP_OKAY, SCIPchgVarUbGlobal(), SCIPisEQ(), SCIPisLT(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by dualcostVarfixing().

◆ redcostAvailable()

static SCIP_Bool redcostAvailable ( SCIP scip)
static

◆ setRedcosts()

static void setRedcosts ( SCIP scip,
SCIP_VAR **  vars,
int  nedges,
SCIP_Real cost 
)
static

initialize reduced costs

Parameters
scipSCIP structure
varsvariables
nedgesnedges
costreduced costs

Definition at line 180 of file prop_stp.c.

References FARAWAY, NULL, SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and SCIPvarIsBinary().

Referenced by dualcostVarfixing(), and reduceRedcostExtended().

◆ setVnoiDistances()

static void setVnoiDistances ( SCIP scip,
const SCIP_Real cost,
const GRAPH graph,
PATH vnoi,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  pathedge,
int *  vbase 
)
static

initialize (Voronoi) distances

Parameters
scipSCIP structure
costreduced costs
graphgraph data structure
vnoiVoronoi paths
costrevreversed reduced costs
pathdistpath distance
pathedgepath edge
vbaseVoronoi base

Definition at line 227 of file prop_stp.c.

References EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_path_execX(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and GRAPH::source.

Referenced by dualcostVarfixing(), and reduceRedcostExtended().

◆ updateFixingBounds()

static void updateFixingBounds ( SCIP_Real fixingbounds,
const GRAPH graph,
const SCIP_Real cost,
const SCIP_Real pathdist,
const PATH vnoi,
SCIP_Real  lpobjal 
)
static

updates fixing bounds for reduced cost fixings

Parameters
fixingboundsfixing bounds
graphgraph data structure
costreduced costs
pathdistshortest path distances
vnoiVoronoi paths
lpobjalLP objective

Definition at line 260 of file prop_stp.c.

References shortest_path::dist, EAT_LAST, GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, and GRAPH::term.

Referenced by dualcostVarfixing().

◆ dualcostVarfixing()

static SCIP_RETCODE dualcostVarfixing ( SCIP scip,
SCIP_Real  lpobjval,
SCIP_VAR **  vars,
SCIP_PROPDATA propdata,
int *  nfixed,
const GRAPH graph 
)
static

dual cost based fixing of variables

Parameters
scipSCIP data structure
lpobjvalLP value
varsvariables
propdatapropagator data
nfixedpointer to number of fixed edges
graphgraph data structure

Definition at line 287 of file prop_stp.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, fixedgevar(), flipedge, globalfixing(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPisGE(), SCIPisGT(), setRedcosts(), setVnoiDistances(), GRAPH::term, and updateFixingBounds().

Referenced by SCIP_DECL_PROPEXEC().

◆ reduceRedcostExtended()

static SCIP_RETCODE reduceRedcostExtended ( SCIP scip,
SCIP_Real  lpobjval,
SCIP_VAR **  vars,
GRAPH propgraph 
)
static

extended reduced cost reduction

Parameters
scipSCIP data structure
lpobjvalLP value
varsvariables
propgraphgraph data structure

Definition at line 367 of file prop_stp.c.

References GRAPH::edges, GRAPH::knots, nnodes, NULL, reduce_extendedEdge(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCutoffbound(), setRedcosts(), setVnoiDistances(), and GRAPH::source.

Referenced by redbasedVarfixing().

◆ redbasedVarfixing()

static SCIP_RETCODE redbasedVarfixing ( SCIP scip,
SCIP_Real  lpobjval,
SCIP_VAR **  vars,
SCIP_PROPDATA propdata,
int *  nfixed,
SCIP_Bool probisinfeas,
const GRAPH g 
)
static

This methods tries to fix edges by performing reductions on the current graph. To this end, the already 0-fixed edges are (temporarily) removed from the underlying graph to strengthen the reduction methods.

Parameters
scipSCIP data structure
lpobjvalLP value
varsvariables
propdatapropagator data
nfixedpointer to number of fixed edges
probisinfeasis problem infeasible?
ggraph data structure

Definition at line 424 of file prop_stp.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, FARAWAY, GRAPH::fixedges, fixedgevar(), flipedge, graph_copy_data(), graph_edge_del(), graph_free_history(), graph_free_historyDeep(), graph_init_history(), graph_knot_chg(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, GRAPH::ieat, Int_List_Node::index, level0(), NULL, Int_List_Node::parent, PROP_STP_EDGE_FIXED, PROP_STP_EDGE_KILLED, PROP_STP_EDGE_SET, PROP_STP_EDGE_UNSET, reduce_contractZeroEdges(), reduceRedcostExtended(), reduceStp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPnodeGetNumber(), SCIPStpBranchruleApplyVertexChgs(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, and TRUE.

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyStp  )
static

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

Definition at line 614 of file prop_stp.c.

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

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeStp  )
static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 629 of file prop_stp.c.

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

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolStp  )
static

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

Definition at line 801 of file prop_stp.c.

References NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolStp  )
static

solving process deinitialization method of propagator (called before branch and bound process data is freed)

Definition at line 823 of file prop_stp.c.

References graph_free(), NULL, SCIP_OKAY, SCIPfreeMemoryArrayNull, SCIPpropGetData(), and TRUE.

◆ fixedgevar()

SCIP_RETCODE fixedgevar ( SCIP scip,
SCIP_VAR edgevar,
int *  nfixed 
)

fix a variable (corresponding to an edge) to zero

Parameters
scipSCIP data structure
edgevarthe variable to be fixed
nfixedcounter that is incriminated if variable could be fixed

Definition at line 848 of file prop_stp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by dualcostVarfixing(), redbasedVarfixing(), and reduce_boundHopRc().

◆ SCIPStpNfixedEdges()

int SCIPStpNfixedEdges ( SCIP scip)

return total number of arcs fixed by 'fixedgevar' method of this propagator

Parameters
scipSCIP data structure

Definition at line 865 of file prop_stp.c.

References NULL, SCIPfindProp(), and SCIPpropGetData().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIPStpPropGetGraph()

void SCIPStpPropGetGraph ( SCIP scip,
GRAPH **  graph,
SCIP_Longint graphnodenumber 
)

gets propagator graph

Parameters
scipSCIP data structure
graphgraph data
graphnodenumberpoint to b&b node for which graph is valid

Definition at line 883 of file prop_stp.c.

References NULL, SCIPfindProp(), and SCIPpropGetData().

◆ SCIPincludePropStp()

SCIP_RETCODE SCIPincludePropStp ( SCIP scip)