Solving Constraint Integer Programs

heur_rec.h File Reference

Detailed Description

Primal recombination heuristic for Steiner problems.

Daniel Rehfeldt

This file implements a recombination heuristic for Steiner problems, see "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano

Definition in file heur_rec.h.

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

Go to the source code of this file.

Data Structures

struct  stp_solution
struct  stp_solution_pool


typedef struct stp_solution STPSOL
typedef struct stp_solution_pool STPSOLPOOL


SCIP_RETCODE SCIPStpHeurRecRun (SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_VAR **vars, int *newsolindex, int runs, int nsols, SCIP_Bool restrictheur, SCIP_Bool *solfound)
STPSOLSCIPStpHeurRecSolfromIdx (STPSOLPOOL *pool, const int soindex)
SCIP_RETCODE SCIPStpHeurRecInitPool (SCIP *scip, STPSOLPOOL **pool, const int nedges, const int maxsize)
SCIP_RETCODE SCIPStpHeurRecAddToPool (SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
void SCIPStpHeurRecFreePool (SCIP *scip, STPSOLPOOL **pool)
SCIP_RETCODE SCIPStpIncludeHeurRec (SCIP *scip)
SCIP_RETCODE SCIPStpHeurRecExclude (SCIP *scip, const GRAPH *graph, const int *result, int *newresult, int *dnodemap, STP_Bool *stvertex, SCIP_Bool *success)

Typedef Documentation


typedef struct stp_solution STPSOL

element of Steiner tree solution pool


typedef struct stp_solution_pool STPSOLPOOL

edge based solution pool for Steiner tree problems (in presolving)

Function Documentation

◆ SCIPStpHeurRecRun()

const GRAPH graph,
SCIP_VAR **  vars,
int *  newsolindex,
int  runs,
int  nsols,
SCIP_Bool  restrictheur,
SCIP_Bool solfound 

run REC heuristic

runs STP recombination heuristic

scipSCIP data structure
poolSTP solution pool or NULL
heurheuristic or NULL
heurdataheuristic data or NULL
graphgraph data
varsvariables or NULL
newsolindexindex of new solution
runsnumber of runs
nsolsnumber of solutions in pool (SCIP or STP)
restrictheuruse restricted version of heur?
solfoundnew solution found?

Definition at line 1025 of file heur_rec.c.

References GRAPH::ancestors, BLOCKED, BMScopyMemoryArray, buildsolgraph(), CONNECT, GRAPH::cost, CYCLES_PER_RUN, EAT_LAST, edgecostmultiplier(), GRAPH::edges, GRAPH::extended, FALSE, GRAPH::fixedges, flipedge, graph_free(), graph_pack(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_term2edgeConsistent(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_valid(), graph_valid(), GRAPH::head, GRAPH::ieat, Int_List_Node::index, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, stp_solution_pool::maxindex, stp_solution_pool::nedges, nnodes, NULL, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, Int_List_Node::parent, GRAPH::pcancestors, GRAPH::prize, REC_MAX_FAILS, reduce(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeMemoryArray, SCIPgetNSols(), SCIPgetSols(), SCIPgetSolVal(), SCIPheurGetData(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPprobdataAddNewSol(), SCIPrandomGetInt(), SCIPsolGetIndex(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), SCIPvarGetUbGlobal(), stp_solution_pool::sols, GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_NWSPG, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeDaSolPcMw(), reduce_da(), and SCIP_DECL_HEUREXEC().

◆ SCIPStpHeurRecSolfromIdx()

STPSOL* SCIPStpHeurRecSolfromIdx ( STPSOLPOOL pool,
const int  soindex 

get solution from index

poolthe pool
soindexthe index

Definition at line 869 of file heur_rec.c.

References stp_solution::index, NULL, stp_solution_pool::size, and stp_solution_pool::sols.

Referenced by computeDaSolPcMw(), and reduce_da().

◆ SCIPStpHeurRecInitPool()

SCIP_RETCODE SCIPStpHeurRecInitPool ( SCIP scip,
STPSOLPOOL **  pool,
const int  nedges,
const int  maxsize 

initializes STPSOL pool

scipSCIP data structure
poolthe pool
nedgesnumber of edges of solutions to be stored in the pool
maxsizecapacity of pool

Definition at line 893 of file heur_rec.c.

References stp_solution_pool::maxindex, stp_solution_pool::maxsize, stp_solution_pool::nedges, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocMemoryArray, stp_solution_pool::size, and stp_solution_pool::sols.

Referenced by reduce_da(), and reduce_daPcMw().

◆ SCIPStpHeurRecAddToPool()

const SCIP_Real  obj,
const int *  soledges,
SCIP_Bool success 

tries to add STPSOL to pool

scipSCIP data structure
objobjective of solution to be added
soledgesedge array of solution to be added
poolthe pool
successhas solution been added?

Definition at line 952 of file heur_rec.c.

References BMScopyMemoryArray, FALSE, stp_solution::index, isInPool(), stp_solution_pool::maxindex, stp_solution_pool::maxsize, stp_solution_pool::nedges, NULL, stp_solution::obj, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocMemoryArray, SCIPdebugMessage, SCIPisGT(), stp_solution_pool::size, stp_solution::soledges, stp_solution_pool::sols, and TRUE.

Referenced by computeDaSolPcMw(), reduce_da(), reduce_daPcMw(), and SCIPStpHeurRecRun().

◆ SCIPStpHeurRecFreePool()

void SCIPStpHeurRecFreePool ( SCIP scip,
STPSOLPOOL **  pool 

frees STPSOL pool

scipSCIP data structure
poolthe pool

Definition at line 924 of file heur_rec.c.

References stp_solution_pool::maxsize, NULL, SCIPfreeBlockMemory, SCIPfreeMemoryArray, stp_solution_pool::size, stp_solution::soledges, and stp_solution_pool::sols.

Referenced by markPcMwRoots(), reduce_da(), and reduce_daPcMw().

◆ SCIPStpIncludeHeurRec()

◆ SCIPStpHeurRecExclude()

SCIP_RETCODE SCIPStpHeurRecExclude ( SCIP scip,
const GRAPH graph,
const int *  result,
int *  newresult,
int *  dnodemap,
STP_Bool stvertex,
SCIP_Bool success 

heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective

scipSCIP data structure
graphgraph structure
resultedge solution array (UNKNOWN/CONNECT)
newresultnew edge solution array (UNKNOWN/CONNECT)
dnodemapnode array for internal use
stvertexnode array for internally marking solution vertices
successsolution improved?

Definition at line 1594 of file heur_rec.c.

References GRAPH::ancestors, BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::fixedges, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exit(), graph_path_init(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, marksolverts(), MIN, nnodes, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, GRAPH::prize, reduce(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPheurGetData(), SCIPisLT(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeDaSolPcMw().