Solving Constraint Integer Programs

heur_ascendprune.h File Reference

Detailed Description

reduction and dual-cost based primal heuristic for Steiner problems

Daniel Rehfeldt

This file implements a reducion and dual-cost 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_ascendprune.h.

#include "scip/scip.h"
#include "grph.h"

Go to the source code of this file.


SCIP_RETCODE SCIPStpIncludeHeurAscendPrune (SCIP *scip)
SCIP_RETCODE SCIPStpHeurAscendPruneRun (SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *edgearrint, int *nodearrint, int root, STP_Bool *nodearrchar, SCIP_Bool *solfound, SCIP_Bool addsol)

Function Documentation

◆ SCIPStpIncludeHeurAscendPrune()

SCIP_RETCODE SCIPStpIncludeHeurAscendPrune ( SCIP scip)

◆ SCIPStpHeurAscendPruneRun()

SCIP_RETCODE SCIPStpHeurAscendPruneRun ( SCIP scip,
const GRAPH g,
const SCIP_Real redcosts,
int *  edgearrint,
int *  nodearrint,
int  root,
STP_Bool nodearrchar,
SCIP_Bool solfound,
SCIP_Bool  addsol 

ascent and prune

scipSCIP data structure
heurheuristic data structure or NULL
gthe graph
redcoststhe reduced costs
edgearrintint edges array to store solution
nodearrintint vertices array for internal computations
rootthe root (used for dual ascent)
nodearrcharSTP_Bool vertices array for internal computations
solfoundhas a solution been found?
addsolshould the solution be added to SCIP by this method?

Definition at line 290 of file heur_ascendprune.c.

References a, BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_init_history(), graph_knot_add(), graph_path_exit(), graph_path_init(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, level0(), GRAPH::mark, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisZero(), SCIPprobdataAddNewSol(), SCIPprobdataGetNVars(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), GRAPH::source, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by computeDaSolPcMw(), computePertubedSol(), reduce_da(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIP_DECL_HEUREXEC(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().