Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Steiner tree relaxator.

Author: Daniel Rehfeldt

Definition in file relax_stp.c.

#include <assert.h>
#include <string.h>
#include "relax_stp.h"
#include "prop_stp.h"
#include "dualascent.h"
#include "solstp.h"

Go to the source code of this file.

Macros
#define	RELAX_NAME "stp"

#define	RELAX_DESC "relaxator for STP"

#define	RELAX_PRIORITY 0

#define	RELAX_FREQ 1

#define	DA_MAXNROOTS 4

Functions
static void	collectRoots (const GRAPH graph, SCIP_RANDNUMGEN randnumgen, int terminals, int nterms)

static SCIP_RETCODE	runDualAscent (SCIP scip, GRAPH graph, SCIP_RANDNUMGEN randnumgen, SCIP_Real lowerbound)

static	SCIP_DECL_RELAXFREE (relaxFreeStp)

static	SCIP_DECL_RELAXINITSOL (relaxInitsolStp)

static	SCIP_DECL_RELAXEXITSOL (relaxExitsolStp)

static	SCIP_DECL_RELAXEXEC (relaxExecStp)

SCIP_Bool	SCIPStpRelaxIsActive (SCIP *scip)

SCIP_RETCODE	SCIPincludeRelaxStp (SCIP *scip)

Macro Definition Documentation

◆ RELAX_NAME

#define RELAX_NAME "stp"

Definition at line 30 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().

◆ RELAX_DESC

#define RELAX_DESC "relaxator for STP"

Definition at line 31 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().

◆ RELAX_PRIORITY

#define RELAX_PRIORITY 0

Definition at line 32 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().

◆ RELAX_FREQ

#define RELAX_FREQ 1

Definition at line 33 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().

◆ DA_MAXNROOTS

#define DA_MAXNROOTS 4

Definition at line 35 of file relax_stp.c.

Referenced by collectRoots().

Function Documentation

◆ collectRoots()

static void collectRoots	(	const GRAPH *	graph,
		SCIP_RANDNUMGEN *	randnumgen,
		int *	terminals,
		int *	nterms
	)

inlinestatic

collects roots

Parameters

graph	graph data structure
randnumgen	random number generator
terminals	terminals array (of size graph->terms)
nterms	number of terminals

Definition at line 58 of file relax_stp.c.

References DA_MAXNROOTS, graph_get_nNodes(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), Is_term, nnodes, SCIP_Bool, SCIPrandomPermuteIntArray(), STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by runDualAscent().

◆ runDualAscent()

static SCIP_RETCODE runDualAscent	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_RANDNUMGEN *	randnumgen,
		SCIP_Real *	lowerbound
	)

static

computes lower bound

Parameters

scip	SCIP data structure
graph	the graph
randnumgen	random number generator
lowerbound	pointer to lower bound (OUT)

Definition at line 109 of file relax_stp.c.

References reduce_cost_parameters::addcuts, reduce_cost_parameters::ascendandprune, collectRoots(), dualascent_exec(), dualascent_execPcMw(), GRAPH::edges, FALSE, graph_path_exit(), graph_path_init(), nterms, NULL, reduce_cost_parameters::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPinfinity(), SCIPrandomGetInt(), solstp_getStpFromSCIPsol(), solstp_rerootInfeas(), STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by SCIP_DECL_RELAXEXEC().

◆ SCIP_DECL_RELAXFREE()

static SCIP_DECL_RELAXFREE ( relaxFreeStp )

static

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

Definition at line 202 of file relax_stp.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeRandom(), SCIPrelaxGetData(), and SCIPrelaxSetData().

◆ SCIP_DECL_RELAXINITSOL()

static SCIP_DECL_RELAXINITSOL ( relaxInitsolStp )

static

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

Definition at line 218 of file relax_stp.c.

References SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetBoolParam(), SCIPrelaxGetData(), and SCIPsetIntParam().

◆ SCIP_DECL_RELAXEXITSOL()

static SCIP_DECL_RELAXEXITSOL ( relaxExitsolStp )

static

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

Definition at line 242 of file relax_stp.c.

References SCIP_OKAY.

◆ SCIP_DECL_RELAXEXEC()

static SCIP_DECL_RELAXEXEC ( relaxExecStp )

static

execution method of relaxator

Definition at line 252 of file relax_stp.c.

References graph_pc_isUnrootedPcMw(), runDualAscent(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPgetCurrentNode(), SCIPinfinity(), SCIPnodeGetNumber(), SCIPprobdataGetGraph2(), SCIPprobdataGetOffset(), SCIPrelaxGetData(), and SCIPStpPropGetGraph().

◆ SCIPStpRelaxIsActive()

SCIP_Bool SCIPStpRelaxIsActive ( SCIP * scip )

is the relaxator active?

Parameters

scip	SCIP data structure

Definition at line 318 of file relax_stp.c.

References SCIPfindRelax(), and SCIPrelaxGetData().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIPincludeRelaxStp()

SCIP_RETCODE SCIPincludeRelaxStp ( SCIP * scip )

creates the stp relaxator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 332 of file relax_stp.c.

References FALSE, NULL, RELAX_DESC, RELAX_FREQ, RELAX_NAME, RELAX_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPcreateRandom(), SCIPincludeRelaxBasic(), SCIPsetRelaxExitsol(), SCIPsetRelaxFree(), SCIPsetRelaxInitsol(), and TRUE.

Referenced by runShell(), and subscipSetupCallbacks().