Detailed Description
reduction-based primal heuristic for Steiner problems
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" |
Definition at line 45 of file heur_ascendprune.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPStpIncludeHeurAscendPrune().
◆ 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
#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE) |
Definition at line 52 of file heur_ascendprune.c.
Referenced by SCIPStpIncludeHeurAscendPrune().
◆ 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 |
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 |
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 |
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()
|
static |
execution method of primal heuristic
Definition at line 148 of file heur_ascendprune.c.
References ASCENPRUNE_MINLPIMPROVE, GRAPH::edges, FALSE, FARAWAY, HEUR_NAME, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetDualbound(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPheurGetData(), SCIPheurGetName(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisGE(), SCIPisLT(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPsolGetIndex(), SCIPStpHeurAscendPruneRun(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), GRAPH::source, and TRUE.
◆ 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
-
scip SCIP data structure heur heuristic data structure or NULL g the graph redcosts the reduced costs edgearrint int edges array to store solution nodearrint int vertices array for internal computations root the root (used for dual ascent) nodearrchar STP_Bool vertices array for internal computations solfound has a solution been found? addsol should 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 | ) |
creates the prune primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 619 of file heur_ascendprune.c.
References DEFAULT_MAXFREQPRUNE, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurFree(), and SCIPsetHeurInit().
Referenced by runShell(), and SCIP_DECL_HEURCOPY().