Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Steiner tree enumeration relaxator.

Author: Daniel Rehfeldt

Definition in file relax_stpenum.c.

#include <assert.h>
#include "relax_stpenum.h"
#include "probdata_stp.h"
#include "prop_stp.h"
#include "mst.h"
#include "solstp.h"
#include "relax_stpdp.h"

Go to the source code of this file.

Macros
#define	RELAX_NAME "stpenum"

#define	RELAX_DESC "enumeration relaxator for STP"

#define	RELAX_PRIORITY 10

#define	RELAX_FREQ 1

#define	ENUM_MAXNSTEINVERTS 8

Functions
static	STP_Vectype (int)

static SCIP_Bool	allTermsAreVisited (const GRAPH graph, const MST mst)

static SCIP_RETCODE	enumExec (SCIP scip, const GRAPH graph, int RESTRICT edges_solstat, SCIP_Real obj)

static SCIP_Bool	enumIsPromising (const GRAPH *graph)

static	SCIP_DECL_RELAXFREE (relaxFreeStpenum)

static	SCIP_DECL_RELAXEXEC (relaxExecStpenum)

SCIP_Bool	SCIPStpEnumRelaxIsPromising (const GRAPH *graph)

SCIP_RETCODE	SCIPStpEnumRelaxComputeSol (SCIP scip, const GRAPH graph, int *RESTRICT edges_solstat)

SCIP_RETCODE	SCIPincludeRelaxStpenum (SCIP *scip)

Macro Definition Documentation

◆ RELAX_NAME

#define RELAX_NAME "stpenum"

Definition at line 31 of file relax_stpenum.c.

Referenced by SCIPincludeRelaxStpenum().

◆ RELAX_DESC

#define RELAX_DESC "enumeration relaxator for STP"

Definition at line 32 of file relax_stpenum.c.

Referenced by SCIPincludeRelaxStpenum().

◆ RELAX_PRIORITY

#define RELAX_PRIORITY 10

Definition at line 33 of file relax_stpenum.c.

Referenced by SCIPincludeRelaxStpenum().

◆ RELAX_FREQ

#define RELAX_FREQ 1

Definition at line 34 of file relax_stpenum.c.

Referenced by SCIPincludeRelaxStpenum().

◆ ENUM_MAXNSTEINVERTS

#define ENUM_MAXNSTEINVERTS 8

Definition at line 36 of file relax_stpenum.c.

Referenced by enumIsPromising(), and STP_Vectype().

Function Documentation

◆ STP_Vectype()

static STP_Vectype ( int )

static

collects and returns all non-terminals graph data structure

Definition at line 50 of file relax_stpenum.c.

References ENUM_MAXNSTEINVERTS, GRAPH::grad, graph_get_nNodes(), Is_term, nnodes, NULL, StpVecGetSize, StpVecPushBack, and GRAPH::term.

Referenced by enumExec().

◆ allTermsAreVisited()

static SCIP_Bool allTermsAreVisited	(	const GRAPH *	graph,
		const MST *	mst
	)

static

are all terminals visited by MST?

Parameters

graph	graph data structure
mst	MST

Definition at line 72 of file relax_stpenum.c.

References FALSE, graph_get_nNodes(), Is_term, nnodes, minimum_spanning_tree::nodes_predEdge, SCIPdebugMessage, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by enumExec(), and updateFromPartition().

◆ enumExec()

static SCIP_RETCODE enumExec	(	SCIP *	scip,
		const GRAPH *	graph,
		int *RESTRICT	edges_solstat,
		SCIP_Real *	obj
	)

static

do enumeration

Parameters

scip	SCIP data structure
graph	graph data structure
edges_solstat	solution edges
obj	optimal objective value

Definition at line 99 of file relax_stpenum.c.

References allTermsAreVisited(), EQ, FALSE, FARAWAY, GRAPH::grad, graph_get_nNodes(), GRAPH::knots, LT, mst_computeOnMarked(), mst_free(), mst_getObj(), mst_getSoledges(), mst_init(), nnodes, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, solstp_getObj(), solstp_isValid(), GRAPH::source, STP_Vectype(), StpVecFree, StpVecGetSize, and TRUE.

Referenced by SCIP_DECL_RELAXEXEC(), and SCIPStpEnumRelaxComputeSol().

◆ enumIsPromising()

static SCIP_Bool enumIsPromising ( const GRAPH * graph )

static

is enumeration promising?

Parameters

graph graph data structure

Definition at line 169 of file relax_stpenum.c.

References ENUM_MAXNSTEINVERTS, FALSE, graph_get_nNodes(), Is_term, nnodes, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by SCIP_DECL_RELAXEXEC(), and SCIPStpEnumRelaxIsPromising().

◆ SCIP_DECL_RELAXFREE()

static SCIP_DECL_RELAXFREE ( relaxFreeStpenum )

static

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

Definition at line 202 of file relax_stpenum.c.

References NULL, SCIP_OKAY, and SCIPrelaxSetData().

◆ SCIP_DECL_RELAXEXEC()

static SCIP_DECL_RELAXEXEC ( relaxExecStpenum )

static

execution method of relaxator

Definition at line 212 of file relax_stpenum.c.

References GRAPH::edges, enumExec(), enumIsPromising(), graph_typeIsSpgLike(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, SCIPgetCurrentNode(), SCIPinfinity(), SCIPnodeGetNumber(), SCIPprobdataGetGraph2(), SCIPStpDpRelaxIsActive(), SCIPStpPropGetGraph(), and solstp_addSolToProb().

◆ SCIPStpEnumRelaxIsPromising()

SCIP_Bool SCIPStpEnumRelaxIsPromising ( const GRAPH * graph )

is using the relaxator promising?

Parameters

graph graph

Definition at line 263 of file relax_stpenum.c.

References enumIsPromising().

Referenced by reduce_redLoopStp(), and SCIPStpEnumRelaxComputeSol().

◆ SCIPStpEnumRelaxComputeSol()

SCIP_RETCODE SCIPStpEnumRelaxComputeSol	(	SCIP *	scip,
		const GRAPH *	graph,
		int *RESTRICT	edges_solstat
	)

Solve instance by enumeration. Only call when promising.

Parameters

scip	SCIP data structure
graph	graph data structure
edges_solstat	solution edges

Definition at line 274 of file relax_stpenum.c.

References enumExec(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPerrorMessage, and SCIPStpEnumRelaxIsPromising().

◆ SCIPincludeRelaxStpenum()

SCIP_RETCODE SCIPincludeRelaxStpenum ( SCIP * scip )

creates the stp relaxator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 296 of file relax_stpenum.c.

References NULL, RELAX_DESC, RELAX_FREQ, RELAX_NAME, RELAX_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPincludeRelaxBasic(), and SCIPsetRelaxFree().

Referenced by runShell().