Detailed Description
generator for global cuts in undirected graphs
Definition in file GomoryHuTree.cpp.
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()
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 |
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 |
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 |
free initialization data structures
Definition at line 148 of file GomoryHuTree.cpp.
References number.
Referenced by ghc_tree().
◆ global_relabel()
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()
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()
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.
Referenced by constructCutList().
◆ constructCutList()
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()
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()
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
|
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
|
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
|
static |
Definition at line 37 of file GomoryHuTree.cpp.
Referenced by global_relabel(), and maxflow().
◆ 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(), SolveWSimplex(), treeAddPendingBdchg(), updateImplicationGraphSOS1(), updateStatistics(), and updateWeightsTCliquegraph().
◆ co_check
|
static |
Definition at line 39 of file GomoryHuTree.cpp.
Referenced by init_maxflow(), and maxflow().