Scippy

SCIP

Solving Constraint Integer Programs

GomoryHuTree.cpp File Reference

Detailed Description

generator for global cuts in undirected graphs

Author
Georg Skorobohatyj
Timo Berthold

Definition in file GomoryHuTree.cpp.

#include <stdio.h>
#include <assert.h>
#include "objscip/objscip.h"
#include "GomoryHuTree.h"

Go to the source code of this file.

Macros

#define EPS   1.0E-10
 

Functions

SCIP_Bool create_graph (int n, int m, GRAPH **gr)
 
static void free_graph (GRAPH **gr)
 
void capture_graph (GRAPH *gr)
 
void release_graph (GRAPH **gr)
 
static SCIP_Bool init_maxflow (long n)
 
static void fini_maxflow (void)
 
static void global_relabel (GRAPH *gr, GRAPHNODE *tptr)
 
static double maxflow (GRAPH *gr, GRAPHNODE *s_ptr, GRAPHNODE *t_ptr)
 
static SCIP_Bool nodeOnRootPath (GRAPH *gr, int i, int j)
 
static void constructCutList (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
 
static void constructSingleCut (GRAPH *gr, SCIP_Bool **cuts)
 
SCIP_Bool ghc_tree (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
 

Variables

static GRAPHNODE ** active
 
static long * number
 
static long max_dist
 
static long bound
 
static SCIP_Bool co_check
 

Macro Definition Documentation

◆ EPS

#define EPS   1.0E-10

epsilon value for numerical comparisons

Definition at line 32 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

Function Documentation

◆ create_graph()

SCIP_Bool create_graph ( int  n,
int  m,
GRAPH **  gr 
)

create a graph

Parameters
nnumber of nodes
mnumber of edges
grpointer to store graph

Definition at line 43 of file GomoryHuTree.cpp.

References BMSallocMemory, BMSallocMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, FALSE, NULL, and TRUE.

Referenced by copy_graph(), and SCIP_DECL_READERREAD().

◆ free_graph()

static void free_graph ( GRAPH **  gr)
static

free a graph

Parameters
grpointer a graph

Definition at line 79 of file GomoryHuTree.cpp.

References BMSfreeMemory, and NULL.

Referenced by release_graph().

◆ capture_graph()

void capture_graph ( GRAPH gr)

◆ release_graph()

◆ init_maxflow()

static SCIP_Bool init_maxflow ( long  n)
static

initialize maximum flow computation

Parameters
nnumber of nodes

Definition at line 119 of file GomoryHuTree.cpp.

References co_check, FALSE, number, and TRUE.

Referenced by ghc_tree().

◆ fini_maxflow()

static void fini_maxflow ( void  )
static

free initialization data structures

Definition at line 148 of file GomoryHuTree.cpp.

References number.

Referenced by ghc_tree().

◆ global_relabel()

static void global_relabel ( GRAPH gr,
GRAPHNODE tptr 
)
static

◆ maxflow()

static double maxflow ( GRAPH gr,
GRAPHNODE s_ptr,
GRAPHNODE t_ptr 
)
static

compute maximum flow

Determines maximum flow and minimum cut between nodes s (= *s_ptr) and t (= *t_ptr) in an undirected graph

References: A. Goldberg/ E. Tarjan: "A New Approach to the Maximum Flow Problem", in Proc. 18th ACM Symp. on Theory of Computing, 1986.

Parameters
grgraph
s_ptrstart node
t_ptrtarget node

Definition at line 254 of file GomoryHuTree.cpp.

References GraphEdge::adjac, GraphNode::alive, GraphEdge::back, GraphNode::bfs_link, bound, GraphEdge::cap, co_check, GraphNode::dist, GRAPH::edges, EPS, GraphNode::excess, FALSE, GraphNode::first_edge, global_relabel(), max_dist, GraphEdge::next, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.

Referenced by ghc_tree().

◆ nodeOnRootPath()

static SCIP_Bool nodeOnRootPath ( GRAPH gr,
int  i,
int  j 
)
static

determine whether node i is on the path to the root starting from j

Parameters
grgraph
inode to search for
jstarting node

Definition at line 553 of file GomoryHuTree.cpp.

References FALSE, and TRUE.

Referenced by constructCutList().

◆ constructCutList()

static void constructCutList ( GRAPH gr,
SCIP_Bool **  cuts,
int *  ncuts,
double  minviol 
)
static

constructs a list of cuts for a TSP relaxation polytope from a Gomory Hu Tree

If the non-zero-edges of a TSP relaxation induce a non-connected graph, an according cut is generated, using information from BFS in method maxflow.

Parameters
grgraph
cutsarray of arrays to store cuts
ncutspointer to store number of cuts
minviolminimal violation of a cut to be returned

Definition at line 576 of file GomoryHuTree.cpp.

References FALSE, and nodeOnRootPath().

Referenced by ghc_tree().

◆ constructSingleCut()

static void constructSingleCut ( GRAPH gr,
SCIP_Bool **  cuts 
)
static

construct a single cut

Parameters
grgraph
cutsarray of arrays to store cuts

Definition at line 600 of file GomoryHuTree.cpp.

References FALSE.

Referenced by ghc_tree().

◆ ghc_tree()

SCIP_Bool ghc_tree ( GRAPH gr,
SCIP_Bool **  cuts,
int *  ncuts,
double  minviol 
)

Determines Gomory/Hu cut tree for input graph with capacitated edges

The tree structures is represented by parent pointers which are part of the node structure, the capacity of a tree edge is stored at the child node, the root of the cut tree is the first node in the list of graph nodes (&gr->nodes[0]). The implementation is described in [1].

References: 1) D. Gusfield: "Very Simple Algorithms and Programs for All Pairs Network Flow Analysis", Computer Science Division, University of California, Davis, 1987.

2) R.E. Gomory and T.C. Hu: "Multi-Terminal Network Flows", SIAM J. Applied Math. 9 (1961), 551-570.

Parameters
grgraph
cutsarray of arrays to store cuts
ncutspointer to store number of cuts
minviolminimal violation of a cut to be returned

Definition at line 623 of file GomoryHuTree.cpp.

References GraphNode::alive, constructCutList(), constructSingleCut(), FALSE, fini_maxflow(), init_maxflow(), maxflow(), GraphNode::mincap, GraphNode::parent, and TRUE.

Referenced by sepaSubtour().

Variable Documentation

◆ active

◆ number

◆ max_dist

long max_dist
static

Definition at line 37 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

◆ bound

◆ co_check

SCIP_Bool co_check
static

Definition at line 39 of file GomoryHuTree.cpp.

Referenced by init_maxflow(), and maxflow().