Detailed Description

generator for global cuts in undirected graphs

Author: Georg Skorobohatyj; Timo Berthold

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

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

n	number of nodes
m	number of edges
gr	pointer 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

gr	pointer 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 )

capture graph

Parameters

gr graph

Definition at line 93 of file GomoryHuTree.cpp.

References NULL.

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 103 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 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

global relabel operation

Parameters

gr	graph
tptr	node to be relabeled

Definition at line 156 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, 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 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(), and sepaspecial_pcimplicationsSeparate().

◆ 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 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

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 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

gr	graph
cuts	array 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

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 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

GRAPHNODE** active

static

Definition at line 35 of file GomoryHuTree.cpp.

Referenced by alnsIncludeNeighborhood(), daExec(), doTableCreate(), dualascent_execPcMw(), global_relabel(), SCIP_DECL_DIALOGEXEC(), SCIP_DECL_SORTPTRCOMP(), SCIPcount(), SCIPdispAutoActivate(), SCIPincludeConsUpgradeNonlinear(), SCIPvarGetProbvarBinary(), and setupProblem().

◆ number

long* number

static

Definition at line 36 of file GomoryHuTree.cpp.

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

◆ max_dist

long max_dist

static

Definition at line 37 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

◆ bound

long bound

static

Definition at line 38 of file GomoryHuTree.cpp.

Referenced by addBdchg(), addCoef(), analyzeGenVBoundConflict(), applyVboundsFixings(), boundPruneHeur(), checkRedundancy(), conflictAddConflictCons(), consdataCreate(), consdataInvalidateActivities(), consdataRecomputeGlbMinactivity(), consdataRecomputeMaxactivity(), consdataRecomputeMinactivity(), convertBoundToInt(), createVarboundCons(), cutsRoundStrongCG(), detectImpliedBounds(), determineBound(), filterExistingLP(), getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), getGenVBoundsMinActivity(), getGenVBoundsMinActivityConflict(), global_relabel(), impliesVlbPrecedenceCondition(), isBoundchgUseless(), maxflow(), nodeGetSolvalBinaryBigMSOS1(), optimize(), performDualfix(), presolRoundIndicator(), redcosts_unifyBlockedEdgeCosts(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduceLurk(), removeFixedVariables(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_DIALOGEXEC(), SCIPapplyHeurDualval(), SCIPlpIsInfeasibilityProved(), SCIPlpiStrongbranch(), SCIPvarGetConflictingBdchgDepth(), SCIPvarGetProbvarBound(), SCIPvarUpdateBestRootSol(), setVarToNearestBound(), treeAddPendingBdchg(), updateImplicationGraphSOS1(), updateStatistics(), and updateWeightsTCliquegraph().

◆ co_check

SCIP_Bool co_check

static

Definition at line 39 of file GomoryHuTree.cpp.

Referenced by init_maxflow(), and maxflow().

SCIP

Detailed Description

Macros

Functions

Variables

Macro Definition Documentation

◆ EPS

Function Documentation

◆ create_graph()

◆ free_graph()

◆ capture_graph()

◆ release_graph()

◆ init_maxflow()

◆ fini_maxflow()

◆ global_relabel()

◆ maxflow()

◆ nodeOnRootPath()

◆ constructCutList()

◆ constructSingleCut()

◆ ghc_tree()

Variable Documentation

◆ active

◆ number

◆ max_dist

◆ bound

◆ co_check