Scippy

SCIP

Solving Constraint Integer Programs

heur_ascendprune.c File Reference

Detailed Description

reduction-based primal heuristic for Steiner problems

Author
Daniel Rehfeldt

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

Definition in file heur_ascendprune.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_ascendprune.h"
#include "heur_local.h"
#include "heur_prune.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   "ascendprune"
 
#define HEUR_DESC   "Dual-cost reduction heuristic for Steiner problems"
 
#define HEUR_DISPCHAR   'A'
 
#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_MAXFREQPRUNE   FALSE
 
#define ASCENPRUNE_MINLPIMPROVE   0.05
 

Functions

static SCIP_DECL_HEURCOPY (heurCopyAscendPrune)
 
static SCIP_DECL_HEURFREE (heurFreeAscendPrune)
 
static SCIP_DECL_HEURINIT (heurInitAscendPrune)
 
static SCIP_DECL_HEUREXEC (heurExecAscendPrune)
 
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)
 
SCIP_RETCODE SCIPStpIncludeHeurAscendPrune (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "ascendprune"

◆ HEUR_DESC

#define HEUR_DESC   "Dual-cost reduction heuristic for Steiner problems"

Definition at line 46 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'A'

Definition at line 47 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   2

Definition at line 48 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 49 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 50 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 51 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 53 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ DEFAULT_MAXFREQPRUNE

#define DEFAULT_MAXFREQPRUNE   FALSE

executions of the heuristic at maximum frequency?

Definition at line 55 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ ASCENPRUNE_MINLPIMPROVE

#define ASCENPRUNE_MINLPIMPROVE   0.05

minimum percentual improvement of dual bound (wrt to gap) mandatory to execute heuristic

Definition at line 56 of file heur_ascendprune.c.

Referenced by SCIP_DECL_HEUREXEC().

Function Documentation

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyAscendPrune  )
static

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

Definition at line 90 of file heur_ascendprune.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeAscendPrune  )
static

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

Definition at line 104 of file heur_ascendprune.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitAscendPrune  )
static

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

Definition at line 126 of file heur_ascendprune.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurAscendPruneRun()

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 
)

ascent and prune

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

◆ SCIPStpIncludeHeurAscendPrune()

SCIP_RETCODE SCIPStpIncludeHeurAscendPrune ( SCIP scip)