Solving Constraint Integer Programs

Detailed Description

reduction-based primal heuristic for Steiner problems

Daniel Rehfeldt

This file implements a reducion based heuristic for Steiner problems. It is based on an approach described in T. Polzin's "Algorithms for the Steiner problem in networks".

Definition in file heur_prune.h.

#include "scip/scip.h"
#include "graph.h"

Go to the source code of this file.


SCIP_RETCODE SCIPStpHeurPruneUpdateSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success)
SCIP_RETCODE SCIPStpIncludeHeurPrune (SCIP *scip)
SCIP_RETCODE SCIPStpHeurPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph)

Function Documentation

◆ SCIPStpHeurPruneUpdateSols()

SCIP_RETCODE SCIPStpHeurPruneUpdateSols ( SCIP scip,
GRAPH prunegraph,
int *  solnode,
int *  soledge,
int *  globalsoledge,
SCIP_Real globalobj,
SCIP_Bool  incumbentgiven,
SCIP_Bool success 

updates solutions for pruned graph

scipSCIP data structure
ggraph data structure
prunegraphpruned graph data structure
solnodearray for best solution nodes wrt prunegraph
soledgearray for best solution edges wrt prunegraph
globalsoledgearray storing best solution wrt g
globalobjpointer to objective value of best solution wrt g
incumbentgivenincumbent solution for pruned graph given?
successpointer to store whether a solution could be found

Definition at line 489 of file heur_prune.c.

References BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, graph_mark(), GRAPH::knots, LT, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisEQ(), SCIPisLE(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), setNodeSolArray(), solstp_getObjBounded(), solstp_getOrg(), solstp_isValid(), STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, TRUE, and UNKNOWN.

Referenced by computeNewSols(), SCIPStpHeurSlackPruneRun(), and updateSolution().

◆ SCIPStpIncludeHeurPrune()

◆ SCIPStpHeurPruneRun()

SCIP_VAR **  vars,
int *  soledge,
SCIP_Bool success,
const SCIP_Bool  withinitialsol,
const SCIP_Bool  reducegraph 

execute prune heuristic on given graph

scipSCIP data structure
varsproblem variables or NULL (need to be provided whenever available)
gthe graph
soledgearray to store primal solution (if no solution is provided, withinitialsol must be set to FALSE)
successfeasible solution found?
withinitialsolsolution given?
reducegraphtry to reduce graph initially?

Definition at line 599 of file heur_prune.c.

References BMScopyMemoryArray, computeNewSols(), CONNECT, bidecomposition_reduction_parameters::depth, reduction_parameters::dualascent, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, getRedBound(), graph_copy(), graph_edge_del(), graph_free(), graph_get_nVET(), graph_initHistory(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, PRUNE_MAXREDROUNDS, PRUNE_MINREDELIMS, reduction_base::redparameters, reduce_boundPruneHeur(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), reduce_solAddNodesol(), reduce_solFree(), reduce_solGetNodesol(), reduce_solGetOffset(), reduce_solInit(), reduce_unconnected(), reduce_unconnectedRpcRmw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPvarGetUbLocal(), setMinMaxElims(), setNodeSolArray(), solstp_getObjBounded(), solstp_isValid(), STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, UNKNOWN, and GRAPH::withInexactReductions.

Referenced by redcostGraphComputeSteinerTree(), and SCIP_DECL_HEUREXEC().