Solving Constraint Integer Programs

GomoryHuTree.h File Reference

Detailed Description

generator for global cuts in undirected graphs

Georg Skorobohatyj
Timo Berthold

Definition in file GomoryHuTree.h.

#include "objscip/objscip.h"

Go to the source code of this file.

Data Structures

struct  GraphNode
struct  GraphEdge
struct  Graph


typedef struct GraphNode GRAPHNODE
typedef struct GraphEdge GRAPHEDGE
typedef struct Graph GRAPH


SCIP_Bool create_graph (int n, int m, GRAPH **gr)
void capture_graph (GRAPH *gr)
void release_graph (GRAPH **gr)
SCIP_Bool ghc_tree (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)

Typedef Documentation


typedef struct GraphNode GRAPHNODE

a node in the graph


typedef struct GraphEdge GRAPHEDGE

an edge in the graph


typedef struct Graph GRAPH

undirected graph

Function Documentation

◆ create_graph()

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

create a graph

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

◆ capture_graph()

void capture_graph ( GRAPH gr)

◆ release_graph()

◆ 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

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.

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