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 "grph.h"
#include "heur_tm.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 DEFAULT_PRUNE_TMRUNS   100
 
#define PRUNE_MINREDELIMS   2
 
#define PRUNE_MAXREDROUNDS   6
 
#define BREAKONERROR   FALSE
 
#define MAXNTERMINALS   500
 
#define MAXNEDGES   10000
 

Functions

static void setNodeSolArray (const GRAPH *g, SCIP_Real *uborg, int *solnode, const int *soledge)
 
static SCIP_RETCODE computeNewSols (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)
 
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, 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 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 44 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 45 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'P'

Definition at line 46 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   2

Definition at line 47 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 48 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 49 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 50 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_TIMING

Definition at line 51 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 52 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 54 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ DEFAULT_PRUNE_TMRUNS

#define DEFAULT_PRUNE_TMRUNS   100

number of runs in TM heuristic when called by prune heuristic

Definition at line 55 of file heur_prune.c.

Referenced by computeNewSols(), and SCIP_DECL_HEURINITSOL().

◆ PRUNE_MINREDELIMS

#define PRUNE_MINREDELIMS   2

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

Definition at line 56 of file heur_prune.c.

Referenced by getRedBound(), and setMinMaxElims().

◆ PRUNE_MAXREDROUNDS

#define PRUNE_MAXREDROUNDS   6

maximum number of reduction rounds in prune heuristic

Definition at line 57 of file heur_prune.c.

Referenced by SCIPStpHeurPruneRun().

◆ BREAKONERROR

#define BREAKONERROR   FALSE

Definition at line 58 of file heur_prune.c.

◆ MAXNTERMINALS

#define MAXNTERMINALS   500

Definition at line 59 of file heur_prune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ MAXNEDGES

#define MAXNEDGES   10000

Definition at line 60 of file heur_prune.c.

Referenced by SCIP_DECL_HEUREXEC().

Function Documentation

◆ setNodeSolArray()

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

◆ computeNewSols()

static SCIP_RETCODE computeNewSols ( 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 
)
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
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 127 of file heur_prune.c.

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

Referenced by SCIPStpHeurPruneRun().

◆ getRedBound()

static int getRedBound ( int  nround,
int  nedges 
)
static

Definition at line 181 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 195 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 248 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 262 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 283 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 293 of file heur_prune.c.

References DEFAULT_PRUNE_TMRUNS, NULL, 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 316 of file heur_prune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

◆ 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 481 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().

◆ SCIPStpHeurPruneRun()

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

◆ SCIPStpIncludeHeurPrune()

SCIP_RETCODE SCIPStpIncludeHeurPrune ( SCIP scip)