Solving Constraint Integer Programs

relax_stp.c File Reference

Detailed Description

Steiner tree relaxator.

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.


#define RELAX_NAME   "stp"
#define RELAX_DESC   "relaxator for STP"
#define RELAX_PRIORITY   0
#define RELAX_FREQ   1
#define DA_MAXNROOTS   4


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


#define RELAX_NAME   "stp"

Definition at line 30 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().


#define RELAX_DESC   "relaxator for STP"

Definition at line 31 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().


#define RELAX_PRIORITY   0

Definition at line 32 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().


#define RELAX_FREQ   1

Definition at line 33 of file relax_stp.c.

Referenced by SCIPincludeRelaxStp().


#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,
int *  terminals,
int *  nterms 

collects roots

graphgraph data structure
randnumgenrandom number generator
terminalsterminals array (of size graph->terms)
ntermsnumber 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_Real lowerbound 


static SCIP_DECL_RELAXFREE ( relaxFreeStp  )

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().


static SCIP_DECL_RELAXINITSOL ( relaxInitsolStp  )

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().


static SCIP_DECL_RELAXEXITSOL ( relaxExitsolStp  )

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.


◆ SCIPStpRelaxIsActive()

SCIP_Bool SCIPStpRelaxIsActive ( SCIP scip)

is the relaxator active?

scipSCIP 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

scipSCIP 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().