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"

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 SCIP_DECL_HEURCOPY ( heurCopyAscendPrune )

static

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

Definition at line 91 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 105 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 127 of file heur_ascendprune.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecAscendPrune )

static

execution method of primal heuristic

Definition at line 149 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 291 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 620 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXFREQPRUNE

◆ ASCENPRUNE_MINLPIMPROVE

Function Documentation

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurAscendPruneRun()

◆ SCIPStpIncludeHeurAscendPrune()