Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions
branch_stp.c File Reference

Detailed Description

Steiner vertex branching rule.

Author
Daniel Rehfeldt

The Steiner branching rule implemented in this file is described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt. It includes and exludes Steiner vertices during branching.

Definition in file branch_stp.c.

#include <assert.h>
#include <string.h>
#include "scip/branch_fullstrong.h"
#include "scip/cons_linear.h"
#include "scip/var.h"
#include "scip/set.h"
#include "scip/pub_tree.h"
#include "scip/struct_scip.h"
#include "scip/clock.h"
#include "grph.h"
#include "branch_stp.h"
#include "probdata_stp.h"

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "stp"
 
#define BRANCHRULE_DESC   "stp branching on vertices"
 
#define BRANCHRULE_PRIORITY   -1000000
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 

Functions

static SCIP_RETCODE selectBranchingVertex (SCIP *scip, int *vertex)
 
static SCIP_DECL_BRANCHCOPY (branchCopyStp)
 
static SCIP_DECL_BRANCHFREE (branchFreeStp)
 
static SCIP_DECL_BRANCHINIT (branchInitStp)
 
static SCIP_DECL_BRANCHEXIT (branchExitStp)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpStp)
 
SCIP_RETCODE SCIPincludeBranchruleStp (SCIP *scip)
 

Macro Definition Documentation

#define BRANCHRULE_DESC   "stp branching on vertices"

Definition at line 40 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 43 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 42 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

#define BRANCHRULE_NAME   "stp"

Definition at line 39 of file branch_stp.c.

Referenced by SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECLP(), and SCIPincludeBranchruleStp().

#define BRANCHRULE_PRIORITY   -1000000

Definition at line 41 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

Function Documentation

static SCIP_DECL_BRANCHCOPY ( branchCopyStp  )
static

copy method for branchrule plugins (called when SCIP copies plugins)

Definition at line 128 of file branch_stp.c.

References BRANCHRULE_NAME, and SCIPincludeBranchruleStp().

static SCIP_DECL_BRANCHEXECLP ( branchExeclpStp  )
static

branching execution method for fractional LP solutions

Definition at line 189 of file branch_stp.c.

References BRANCHRULE_NAME, EAT_LAST, FALSE, flipedge, GRAPH::ieat, GRAPH::inpbeg, SCIPprobdataGetEdgeVars(), SCIPprobdataGetGraph(), selectBranchingVertex(), TRUE, and UNKNOWN.

static SCIP_DECL_BRANCHEXIT ( branchExitStp  )
static

deinitialization method of branching rule (called before transformed problem is freed)

Definition at line 172 of file branch_stp.c.

static SCIP_DECL_BRANCHFREE ( branchFreeStp  )
static

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

Definition at line 142 of file branch_stp.c.

static SCIP_DECL_BRANCHINIT ( branchInitStp  )
static

initialization method of branching rule (called after problem was transformed)

Definition at line 158 of file branch_stp.c.

SCIP_RETCODE SCIPincludeBranchruleStp ( SCIP *  scip)

creates the multi-aggregated branching rule and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 277 of file branch_stp.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, and BRANCHRULE_PRIORITY.

Referenced by runShell(), and SCIP_DECL_BRANCHCOPY().

static SCIP_RETCODE selectBranchingVertex ( SCIP *  scip,
int *  vertex 
)
static
Parameters
sciporiginal SCIP data structure
vertexthe vertex to branch on

Definition at line 62 of file branch_stp.c.

References EAT_LAST, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, SCIPprobdataGetEdgeVars(), SCIPprobdataGetGraph(), GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_BRANCHEXECLP().