Scippy

SCIP

Solving Constraint Integer Programs

heur_rec.h File Reference

Detailed Description

Primal recombination heuristic for Steiner problems.

Author
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
 

Typedefs

typedef struct stp_solution STPSOL
 
typedef struct stp_solution_pool STPSOLPOOL
 

Functions

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

◆ STPSOL

typedef struct stp_solution STPSOL

element of Steiner tree solution pool

◆ STPSOLPOOL

typedef struct stp_solution_pool STPSOLPOOL

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

Function Documentation

◆ SCIPStpHeurRecRun()

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 
)

run REC heuristic

runs STP recombination heuristic

Parameters
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

Parameters
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

Parameters
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()

SCIP_RETCODE SCIPStpHeurRecAddToPool ( SCIP scip,
const SCIP_Real  obj,
const int *  soledges,
STPSOLPOOL pool,
SCIP_Bool success 
)

tries to add STPSOL to pool

Parameters
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

Parameters
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

Parameters
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().