relax_stpdp.c File Reference

Detailed Description

Steiner tree relaxator.

Author

Daniel Rehfeldt

Definition in file relax_stpdp.c.

#include <assert.h>
#include <string.h>
#include "relax_stpdp.h"
#include "probdata_stp.h"
#include "solstp.h"
#include "dpterms.h"
#include "dpborder.h"
#include "substpsolver.h"

Go to the source code of this file.

Macros
#define	RELAX_NAME   "stpdp"
#define	RELAX_DESC   "DP relaxator for STP"
#define	RELAX_PRIORITY   100000000
#define	RELAX_FREQ   1

Enumerations
enum	DP_TYPE {   dp_border,   dp_terms }

Functions
static SCIP_RETCODE	solveWithDpBorder (SCIP *scip, GRAPH *graph, DPBORDER *dpborder, SCIP_Real *obj, SCIP_Bool *wasSolved)
static SCIP_RETCODE	solveWithDpTerms (SCIP *scip, GRAPH *graph, SCIP_Real *obj, SCIP_Bool *wasSolved)
static	SCIP_DECL_RELAXFREE (relaxFreeStpdp)
static	SCIP_DECL_RELAXINITSOL (relaxInitsolStpdp)
static	SCIP_DECL_RELAXEXITSOL (relaxExitsolStpdp)
static	SCIP_DECL_RELAXEXEC (relaxExecStpdp)
SCIP_Bool	SCIPStpDpRelaxIsPromising (SCIP *scip, GRAPH *graph)
SCIP_RETCODE	SCIPStpDpRelaxActivate (SCIP *scip)
SCIP_Bool	SCIPStpDpRelaxIsActive (SCIP *scip)
SCIP_RETCODE	SCIPincludeRelaxStpdp (SCIP *scip)

Macro Definition Documentation

RELAX_NAME

#define RELAX_NAME   "stpdp"

Definition at line 34 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

RELAX_DESC

#define RELAX_DESC   "DP relaxator for STP"

Definition at line 35 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

RELAX_PRIORITY

#define RELAX_PRIORITY   100000000

Definition at line 36 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

RELAX_FREQ

#define RELAX_FREQ   1

Definition at line 37 of file relax_stpdp.c.

Referenced by SCIPincludeRelaxStpdp().

Enumeration Type Documentation

DP_TYPE

enum DP_TYPE

Enumerator
dp_border
dp_terms

Definition at line 39 of file relax_stpdp.c.

Function Documentation

solveWithDpBorder()

static SCIP_RETCODE solveWithDpBorder ( SCIP *  scip, GRAPH *  graph, DPBORDER *  dpborder, SCIP_Real *  obj, SCIP_Bool *  wasSolved  )

static

solves problem with border-FPT DP

Parameters

scip	SCIP data structure
graph	the graph
dpborder	DP border algorithm data structure
obj	pointer to the objective value (OUT)
wasSolved	pointer to mark whether problem was solved (OUT)

Definition at line 62 of file relax_stpdp.c.

References dpborder_solve(), GRAPH::edges, graph_printInfo(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_addSolToProb(), and solstp_getObj().

Referenced by SCIP_DECL_RELAXEXEC().

solveWithDpTerms()

static SCIP_RETCODE solveWithDpTerms ( SCIP *  scip, GRAPH *  graph, SCIP_Real *  obj, SCIP_Bool *  wasSolved  )

static

solves problem with terminals-FPT DP

Parameters

scip	SCIP data structure
graph	the graph
obj	pointer to the objective value (OUT)
wasSolved	pointer to mark whether problem was solved (OUT)

Definition at line 103 of file relax_stpdp.c.

References dpterms_solve(), GRAPH::edges, EQ, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_addSolToProb(), solstp_getObj(), and substpsolver_getObjFromGraph().

Referenced by SCIP_DECL_RELAXEXEC().

SCIP_DECL_RELAXFREE()

static SCIP_DECL_RELAXFREE ( relaxFreeStpdp  )

static

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

Definition at line 155 of file relax_stpdp.c.

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

SCIP_DECL_RELAXINITSOL()

static SCIP_DECL_RELAXINITSOL ( relaxInitsolStpdp  )

static

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

Definition at line 172 of file relax_stpdp.c.

References SCIP_OKAY.

SCIP_DECL_RELAXEXITSOL()

static SCIP_DECL_RELAXEXITSOL ( relaxExitsolStpdp  )

static

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

Definition at line 185 of file relax_stpdp.c.

References SCIP_OKAY.

SCIP_DECL_RELAXEXEC()

static SCIP_DECL_RELAXEXEC ( relaxExecStpdp  )

static

execution method of relaxator

Definition at line 194 of file relax_stpdp.c.

References dp_border, dp_terms, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPinfinity(), SCIPisStopped(), SCIPprobdataGetGraph2(), SCIPrelaxGetData(), solveWithDpBorder(), and solveWithDpTerms().

SCIPStpDpRelaxIsPromising()

SCIP_Bool SCIPStpDpRelaxIsPromising	(	SCIP *	scip,
		GRAPH *	graph
	)

is using the relaxator promising?

Parameters

scip	SCIP data structure
graph	graph

Definition at line 239 of file relax_stpdp.c.

References dp_border, dp_terms, dpborder_init(), dpborder_probePotential(), dpterms_isPromisingPartly(), FALSE, SCIP_Bool, SCIP_CALL, SCIPfindRelax(), SCIPrelaxGetData(), and TRUE.

Referenced by SCIPprobdataCreateFromGraph().

SCIPStpDpRelaxActivate()

SCIP_RETCODE SCIPStpDpRelaxActivate

(

SCIP *

scip

)

activates

Parameters

scip	SCIP data structure

Definition at line 272 of file relax_stpdp.c.

References SCIP_CALL, SCIP_OKAY, SCIPfindRelax(), SCIPrelaxGetData(), SCIPsetIntParam(), and TRUE.

Referenced by SCIPprobdataCreateFromGraph().

SCIPStpDpRelaxIsActive()

SCIP_Bool SCIPStpDpRelaxIsActive

(

SCIP *

scip

)

is active?

Parameters

scip	SCIP data structure

Definition at line 293 of file relax_stpdp.c.

References SCIPfindRelax(), and SCIPrelaxGetData().

Referenced by SCIP_DECL_RELAXEXEC().

SCIPincludeRelaxStpdp()

SCIP_RETCODE SCIPincludeRelaxStpdp

(

SCIP *

scip

)

creates the relaxator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 307 of file relax_stpdp.c.

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

Referenced by runShell(), and subscipSetupCallbacks().