Scippy

SCIP

Solving Constraint Integer Programs

heur_prune.c File Reference

Detailed Description

reduction-based primal heuristic for Steiner problems

Author
Daniel Rehfeldt

This file implements a reduction based heuristic for Steiner problems. See "SCIP-Jack - A solver for STP and variants with parallelization extensions" (2016) by Gamrath, Koch, Maher, Rehfeldt and Shinano

A list of all interface methods can be found in heur_prune.h

Definition in file heur_prune.c.

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "heur_prune.h"
#include "heur_local.h"
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "solstp.h"
#include "cons_stp.h"
#include "scip/pub_misc.h"
#include "probdata_stp.h"

Go to the source code of this file.

Macros

#define HEUR_NAME   "prune"
 
#define HEUR_DESC   "Reduction based heuristic for Steiner problems"
 
#define HEUR_DISPCHAR   'P'
 
#define HEUR_PRIORITY   2
 
#define HEUR_FREQ   -1
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
 
#define HEUR_USESSUBSCIP   FALSE
 
#define DEFAULT_PRUNE_MAXFRQ   FALSE
 
#define PRUNE_TMRUNS   100
 
#define PRUNE_TMRUNS_FAST   70
 
#define PRUNE_MINREDELIMS   2
 
#define PRUNE_MAXREDROUNDS   6
 
#define MAXNTERMINALS   500
 
#define MAXNEDGES   10000
 

Functions

static void setNodeSolArray (const GRAPH *g, SCIP_Real *RESTRICT uborg, int *RESTRICT solnode, const int *soledge)
 
static SCIP_RETCODE computeNewSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *nodearrint, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool beFast, SCIP_Bool *success)
 
static int getRedBound (int nround, int nedges)
 
static void setMinMaxElims (SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxrounds)
 
static SCIP_DECL_HEURCOPY (heurCopyPrune)
 
static SCIP_DECL_HEURFREE (heurFreePrune)
 
static SCIP_DECL_HEURINIT (heurInitPrune)
 
static SCIP_DECL_HEURINITSOL (heurInitsolPrune)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolPrune)
 
static SCIP_DECL_HEUREXEC (heurExecPrune)
 
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 SCIPStpHeurPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph)
 
SCIP_RETCODE SCIPStpIncludeHeurPrune (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "prune"

Definition at line 46 of file heur_prune.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPStpIncludeHeurPrune().

◆ HEUR_DESC

#define HEUR_DESC   "Reduction based heuristic for Steiner problems"

Definition at line 47 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'P'

Definition at line 48 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   2

Definition at line 49 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 50 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 51 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 52 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_TIMING

Definition at line 53 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 54 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ DEFAULT_PRUNE_MAXFRQ

#define DEFAULT_PRUNE_MAXFRQ   FALSE

executions of the heuristic at maximum frequency?

Definition at line 56 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ PRUNE_TMRUNS

#define PRUNE_TMRUNS   100

number of runs in TM heuristic when called by prune heuristic

Definition at line 57 of file heur_prune.c.

Referenced by computeNewSols(), and SCIP_DECL_HEURINITSOL().

◆ PRUNE_TMRUNS_FAST

#define PRUNE_TMRUNS_FAST   70

number of runs in TM heuristic when called by prune heuristic

Definition at line 58 of file heur_prune.c.

◆ PRUNE_MINREDELIMS

#define PRUNE_MINREDELIMS   2

maximum number of eliminations for reduction package when called by prune heuristic

Definition at line 59 of file heur_prune.c.

Referenced by getRedBound(), SCIPStpHeurPruneRun(), and setMinMaxElims().

◆ PRUNE_MAXREDROUNDS

#define PRUNE_MAXREDROUNDS   6

maximum number of reduction rounds in prune heuristic

Definition at line 60 of file heur_prune.c.

Referenced by SCIPStpHeurPruneRun().

◆ MAXNTERMINALS

#define MAXNTERMINALS   500

Definition at line 61 of file heur_prune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ MAXNEDGES

#define MAXNEDGES   10000

Definition at line 62 of file heur_prune.c.

Referenced by SCIP_DECL_HEUREXEC().

Function Documentation

◆ setNodeSolArray()

static void setNodeSolArray ( const GRAPH g,
SCIP_Real *RESTRICT  uborg,
int *RESTRICT  solnode,
const int *  soledge 
)
static

◆ computeNewSols()

static SCIP_RETCODE computeNewSols ( SCIP scip,
GRAPH g,
GRAPH prunegraph,
int *  nodearrint,
int *  solnode,
int *  soledge,
int *  globalsoledge,
SCIP_Real globalobj,
SCIP_Bool  incumbentgiven,
SCIP_Bool  beFast,
SCIP_Bool success 
)
static

computes new solution during execution of prune and updates best global one if possible

Parameters
scipSCIP data structure
ggraph data structure
prunegraphpruned graph data structure
nodearrintarray
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?
beFastuse fast mode?
successpointer to store whether a solution could be found

Definition at line 131 of file heur_prune.c.

References GRAPH::cost, GRAPH::edges, GRAPH::grad, graph_valid(), GRAPH::knots, GRAPH::mark, nnodes, NULL, pcmode_fromheurdata, PRUNE_TMRUNS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), GRAPH::source, and GRAPH::terms.

Referenced by SCIPStpHeurPruneRun().

◆ getRedBound()

static int getRedBound ( int  nround,
int  nedges 
)
static

Definition at line 191 of file heur_prune.c.

References MAX, and PRUNE_MINREDELIMS.

Referenced by SCIPStpHeurPruneRun().

◆ setMinMaxElims()

static void setMinMaxElims ( SCIP scip,
int *  minnelims,
int *  lminnelims,
int  annodes,
int  anedges,
int  anterms,
int  nround,
int  maxrounds 
)
static

Definition at line 206 of file heur_prune.c.

References MAX, NULL, PRUNE_MINREDELIMS, SCIP_Real, and SCIPisGT().

Referenced by SCIPStpHeurPruneRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyPrune  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 258 of file heur_prune.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurPrune().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreePrune  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 272 of file heur_prune.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitPrune  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 293 of file heur_prune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolPrune  )
static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 303 of file heur_prune.c.

References NULL, PRUNE_TMRUNS, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolPrune  )
static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 326 of file heur_prune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurPruneUpdateSols()

SCIP_RETCODE SCIPStpHeurPruneUpdateSols ( SCIP scip,
GRAPH g,
GRAPH prunegraph,
int *  solnode,
int *  soledge,
int *  globalsoledge,
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
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().

◆ SCIPStpHeurPruneRun()

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

execute prune heuristic on given graph

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

◆ SCIPStpIncludeHeurPrune()