Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

reduction-based primal heuristic for Steiner problems

Author
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 "grph.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPStpHeurPruneUpdateSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, PATH *path, int *nodearrint, int *edgearrint, int *solnode, int *soledge, int *globalsoledge, STP_Bool *nodearrchar, 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 g,
GRAPH prunegraph,
PATH path,
int *  nodearrint,
int *  edgearrint,
int *  solnode,
int *  soledge,
int *  globalsoledge,
STP_Bool nodearrchar,
SCIP_Real globalobj,
SCIP_Bool  incumbentgiven,
SCIP_Bool success 
)

updates solutions for pruned graph

Parameters
scipSCIP data structure
ggraph data structure
prunegraphpruned graph data structure
pathshortest path struct
nodearrintarray
edgearrintarray
solnodearray for best solution nodes wrt prunegraph
soledgearray for best solution edges wrt prunegraph
globalsoledgearray storing best solution wrt g
nodearrchararray
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 482 of file heur_prune.c.

References BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, FARAWAY, GRAPH::grad, graph_sol_getObj(), graph_sol_getOrg(), graph_sol_valid(), GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), setNodeSolArray(), STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, TRUE, and UNKNOWN.

Referenced by computeNewSols(), and SCIPStpHeurSlackPruneRun().

◆ SCIPStpIncludeHeurPrune()

SCIP_RETCODE SCIPStpIncludeHeurPrune ( SCIP scip)

◆ SCIPStpHeurPruneRun()

SCIP_RETCODE SCIPStpHeurPruneRun ( SCIP scip,
SCIP_VAR **  vars,
GRAPH g,
int *  soledge,
SCIP_Bool success,
const SCIP_Bool  withinitialsol,
const SCIP_Bool  reducegraph 
)