Detailed Description
propagator for Steiner tree problems, using the LP reduced costs
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
#define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 41 of file prop_stp.c.
Referenced by SCIPincludePropStp().
◆ PROP_PRIORITY
#define PROP_PRIORITY 1000000 |
◆ PROP_FREQ
#define PROP_FREQ 1 |
◆ 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 |
try to make global fixings
- Parameters
-
scip SCIP structure vars variables nfixededges points to number of fixed edges fixingbounds fixing bounds graph graph structure cutoffbound cutoff bound nedges number of edges
Definition at line 121 of file prop_stp.c.
References SCIP_OKAY, SCIPchgVarUbGlobal(), SCIPisEQ(), SCIPisLT(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by dualcostVarfixing().
◆ redcostAvailable()
- Parameters
-
scip SCIP structure
Definition at line 151 of file prop_stp.c.
References FALSE, SCIP_LPSOLSTAT_OPTIMAL, SCIPgetCutoffbound(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisInfinity(), SCIPisLPRelax(), SCIPisLPSolBasic(), and TRUE.
Referenced by SCIP_DECL_PROPEXEC().
◆ setRedcosts()
initialize reduced costs
- Parameters
-
scip SCIP structure vars variables nedges nedges cost reduced 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 |
initialize (Voronoi) distances
- Parameters
-
scip SCIP structure cost reduced costs graph graph data structure vnoi Voronoi paths costrev reversed reduced costs pathdist path distance pathedge path edge vbase Voronoi 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 |
updates fixing bounds for reduced cost fixings
- Parameters
-
fixingbounds fixing bounds graph graph data structure cost reduced costs pathdist shortest path distances vnoi Voronoi paths lpobjal LP 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 |
dual cost based fixing of variables
- Parameters
-
scip SCIP data structure lpobjval LP value vars variables propdata propagator data nfixed pointer to number of fixed edges graph graph 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 |
extended reduced cost reduction
- Parameters
-
scip SCIP data structure lpobjval LP value vars variables propgraph graph 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 |
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
-
scip SCIP data structure lpobjval LP value vars variables propdata propagator data nfixed pointer to number of fixed edges probisinfeas is problem infeasible? g graph 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 |
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 |
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()
|
static |
reduced cost propagation method for an LP solution
Definition at line 647 of file prop_stp.c.
References BLOCKED, GRAPH::cost, dualcostVarfixing(), GRAPH::edges, FALSE, graph_copy(), graph_init_history(), NULL, redbasedVarfixing(), redcostAvailable(), REDUCTION_WAIT_RATIO, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMessage, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetNPseudoBranchCands(), SCIPgetProbData(), SCIPgetStage(), SCIPisGT(), SCIPnodeGetNumber(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPpropGetData(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), STP_DCSTP, STP_PCSPG, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, and TRUE.
◆ SCIP_DECL_PROPINITSOL()
|
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 |
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
-
scip SCIP data structure edgevar the variable to be fixed nfixed counter 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
-
scip SCIP 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
-
scip SCIP data structure graph graph data graphnodenumber point 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 | ) |
creates the stp propagator and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 904 of file prop_stp.c.
References DEFAULT_MAXNWAITINGROUNDS, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludePropBasic(), SCIPsetPropCopy(), SCIPsetPropExitsol(), SCIPsetPropFree(), and SCIPsetPropInitsol().
Referenced by runShell(), and SCIP_DECL_PROPCOPY().