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 41 of file GomoryHuTree.cpp.

Function Documentation

create_graph()

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

create a graph

Parameters

n	number of nodes
m	number of edges
gr	pointer to store graph

Definition at line 52 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

gr	pointer a graph

Definition at line 88 of file GomoryHuTree.cpp.

References BMSfreeMemory, and NULL.

Referenced by release_graph().

capture_graph()

void capture_graph

(

GRAPH *

gr

)

capture graph

Parameters

gr

graph

Definition at line 102 of file GomoryHuTree.cpp.

References NULL, and Graph::nuses.

Referenced by tsp::ProbDataTSP::ProbDataTSP(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSTRANS(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and tsp::SCIPcreateConsSubtour().

release_graph()

void release_graph

(

GRAPH **

gr

)

release graph

Parameters

gr

graph

Definition at line 112 of file GomoryHuTree.cpp.

References free_graph(), and NULL.

Referenced by tsp::ProbDataTSP::scip_copy(), SCIP_DECL_CONSDELETE(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_READERREAD(), tsp::ProbDataTSP::scip_delorig(), tsp::ProbDataTSP::scip_deltrans(), tsp::ProbDataTSP::scip_trans(), tsp::HeurFarthestInsert::~HeurFarthestInsert(), and tsp::ProbDataTSP::~ProbDataTSP().

init_maxflow()

static SCIP_Bool init_maxflow ( long  n )

static

initialize maximum flow computation

Parameters

n	number of nodes

Definition at line 128 of file GomoryHuTree.cpp.

References active, 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 157 of file GomoryHuTree.cpp.

References active, and number.

Referenced by ghc_tree().

global_relabel()

static void global_relabel ( GRAPH *  gr, GRAPHNODE *  tptr  )

static

global relabel operation

Parameters

gr	graph
tptr	node to be relabeled

Definition at line 165 of file GomoryHuTree.cpp.

References active, GraphEdge::adjac, GraphNode::alive, GraphEdge::back, GraphNode::bfs_link, bound, GraphEdge::cap, GraphNode::dist, EPS, GraphNode::excess, FALSE, GraphNode::first_edge, max_dist, GraphEdge::next, Graph::nnodes, Graph::nodes, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.

Referenced by maxflow().

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

gr	graph
s_ptr	start node
t_ptr	target node

Definition at line 263 of file GomoryHuTree.cpp.

References active, 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, Graph::nedges, Graph::nedgesnonzero, GraphEdge::next, Graph::nnodes, Graph::nodes, 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

gr	graph
i	node to search for
j	starting node

Definition at line 562 of file GomoryHuTree.cpp.

References FALSE, GraphNode::id, Graph::nodes, GraphNode::parent, 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

gr	graph
cuts	array of arrays to store cuts
ncuts	pointer to store number of cuts
minviol	minimal violation of a cut to be returned

Definition at line 585 of file GomoryHuTree.cpp.

References FALSE, GraphNode::mincap, Graph::nnodes, nodeOnRootPath(), and Graph::nodes.

Referenced by ghc_tree().

constructSingleCut()

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

static

construct a single cut

Parameters

gr	graph
cuts	array of arrays to store cuts

Definition at line 609 of file GomoryHuTree.cpp.

References FALSE, Graph::nnodes, Graph::nodes, and GraphNode::unmarked.

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

gr	graph
cuts	array of arrays to store cuts
ncuts	pointer to store number of cuts
minviol	minimal violation of a cut to be returned

Definition at line 632 of file GomoryHuTree.cpp.

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

Referenced by sepaSubtour().

Variable Documentation

active

GRAPHNODE** active

static

Definition at line 44 of file GomoryHuTree.cpp.

Referenced by addSSTConssOrbitAndUpdateSST(), alnsIncludeNeighborhood(), doTableCreate(), fini_maxflow(), global_relabel(), init_maxflow(), maxflow(), schedulerIncludeNeighborhood(), SCIP_DECL_DIALOGEXEC(), SCIP_DECL_SORTPTRCOMP(), SCIPconssetchgAddAddedCons(), SCIPcount(), SCIPdispAutoActivate(), SCIPincludeConsUpgradeNonlinear(), SCIPincludeTable(), SCIPtableCreate(), SCIPvarGetProbvarBinary(), selectOrbitLeaderSSTConss(), setupProblem(), and updateSymInfoConflictGraphSST().

number

long* number

static

Definition at line 45 of file GomoryHuTree.cpp.

Referenced by fini_maxflow(), getNJobs(), getNResources(), global_relabel(), init_maxflow(), maxflow(), mpsinputReadLine(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_SORTPTRCOMP().

max_dist

long max_dist

static

Definition at line 46 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

bound

long bound

static

Definition at line 47 of file GomoryHuTree.cpp.

Referenced by addBdchg(), addCoef(), addConflictReasonVars(), addSymmetryInformation(), analyzeConflictRangedRow(), analyzeGenVBoundConflict(), applyBoundChgs(), applyObbt(), applyVboundsFixings(), checkRedundancy(), collectMinactImplicVars(), collectMinactObjchg(), conflictAddConflictCons(), consdataComputePseudoActivity(), consdataCreate(), consdataRecomputeGlbMaxactivity(), consdataRecomputeGlbMinactivity(), consdataRecomputeMaxactivity(), consdataRecomputeMinactivity(), convertBoundToInt(), convertToActiveVar(), createGenVBound(), createVarboundCons(), cutsRoundStrongCG(), detectImpliedBounds(), determineBound(), evalBound(), filterBounds(), filterExistingLP(), filterRound(), getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), getGenVBoundsMinActivity(), getGenVBoundsMinActivityConflict(), getMaxactImplicObjchg(), getMaxactObjchg(), getMinactImplicObjchg(), getMinactObjchg(), getScore(), getVarObjchg(), global_relabel(), impliesVlbPrecedenceCondition(), isBoundchgUseless(), maxflow(), nodeGetSolvalBinaryBigMSOS1(), optimize(), performDualfix(), presolRoundIndicator(), provedBound(), rangedRowPropagation(), removeFixedVariables(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_DIALOGEXEC(), SCIPaddReoptnodeBndchg(), SCIPapplyHeurDualval(), SCIPapplyProbingVar(), SCIPlpGetProvedLowerbound(), SCIPlpIsInfeasibilityProved(), SCIPlpiStrongbranch(), SCIPvarGetConflictingBdchgDepth(), SCIPvarGetProbvarBound(), SCIPvarUpdateBestRootSol(), sepastoreApplyLb(), sepastoreApplyUb(), setObjProbing(), setVarToNearestBound(), TCLIQUE_NEWSOL(), tightenBoundProbing(), treeAddPendingBdchg(), updateImplicationGraphSOS1(), updateStatistics(), and updateWeightsTCliquegraph().

co_check

SCIP_Bool co_check

static

Definition at line 48 of file GomoryHuTree.cpp.

Referenced by init_maxflow(), and maxflow().