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) |
SCIP_Bool | init_maxflow (long n) |
void | fini_maxflow () |
void | global_relabel (GRAPH *gr, GRAPHNODE *tptr) |
double | maxflow (GRAPH *gr, GRAPHNODE *s_ptr, GRAPHNODE *t_ptr) |
SCIP_Bool | nodeOnRootPath (GRAPH *gr, int i, int j) |
void | constructCutList (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol) |
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 |
#define EPS 1.0E-10 |
Definition at line 31 of file GomoryHuTree.cpp.
Referenced by global_relabel(), and maxflow().
Definition at line 38 of file GomoryHuTree.cpp.
References BMSallocMemory, BMSallocMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, FALSE, and TRUE.
Referenced by copy_graph(), and SCIP_DECL_READERREAD().
|
static |
Definition at line 68 of file GomoryHuTree.cpp.
References BMSfreeMemory.
Referenced by release_graph().
void capture_graph | ( | GRAPH * | gr | ) |
Definition at line 78 of file GomoryHuTree.cpp.
References Graph::nuses.
Referenced by tsp::ProbDataTSP::ProbDataTSP(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSTRANS(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and tsp::SCIPcreateConsSubtour().
void release_graph | ( | GRAPH ** | gr | ) |
Definition at line 84 of file GomoryHuTree.cpp.
References free_graph().
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().
SCIP_Bool init_maxflow | ( | long | n | ) |
Definition at line 94 of file GomoryHuTree.cpp.
References co_check, FALSE, number, and TRUE.
Referenced by ghc_tree().
void fini_maxflow | ( | ) |
Definition at line 126 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, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.
Referenced by maxflow().
Definition at line 207 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, Graph::nedges, Graph::nedgesnonzero, GraphEdge::next, Graph::nnodes, Graph::nodes, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.
Referenced by ghc_tree().
Definition at line 500 of file GomoryHuTree.cpp.
References FALSE, GraphNode::id, Graph::nodes, GraphNode::parent, and TRUE.
Referenced by constructCutList().
Definition at line 513 of file GomoryHuTree.cpp.
References FALSE, GraphNode::mincap, Graph::nnodes, nodeOnRootPath(), and Graph::nodes.
Referenced by ghc_tree().
Definition at line 531 of file GomoryHuTree.cpp.
References FALSE, Graph::nnodes, Graph::nodes, and GraphNode::unmarked.
Referenced by ghc_tree().
Definition at line 538 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().
|
static |
Definition at line 33 of file GomoryHuTree.cpp.
Referenced by alnsIncludeNeighborhood(), global_relabel(), SCIP_DECL_DIALOGEXEC(), SCIP_DECL_SORTPTRCOMP(), SCIPcount(), SCIPdispAutoActivate(), SCIPincludeNonlinconsUpgrade(), SCIPincludeQuadconsUpgrade(), SCIPtableCreate(), SCIPvarGetProbvarBinary(), and setupProblem().
|
static |
Definition at line 34 of file GomoryHuTree.cpp.
Referenced by exprParse(), fini_maxflow(), global_relabel(), init_maxflow(), maxflow(), mpsinputReadLine(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_SORTPTRCOMP().
|
static |
Definition at line 35 of file GomoryHuTree.cpp.
Referenced by global_relabel(), and maxflow().
|
static |
Definition at line 35 of file GomoryHuTree.cpp.
Referenced by addBdchg(), addCoef(), analyzeGenVBoundConflict(), applyVboundsFixings(), checkRedundancy(), conflictAddConflictCons(), consdataComputePseudoActivity(), consdataCreate(), consdataInvalidateActivities(), consdataRecomputeGlbMinactivity(), consdataRecomputeMaxactivity(), consdataRecomputeMinactivity(), detectImpliedBounds(), determineBound(), filterExistingLP(), getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), getGenVBoundsMinActivity(), getGenVBoundsMinActivityConflict(), global_relabel(), impliesVlbPrecedenceCondition(), isBoundchgUseless(), maxflow(), nodeGetSolvalBinaryBigMSOS1(), optimize(), performDualfix(), presolRoundIndicator(), removeFixedVariables(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_DIALOGEXEC(), SCIPapplyHeurDualval(), SCIPlpIsInfeasibilityProved(), SCIPvarGetConflictingBdchgDepth(), SCIPvarGetProbvarBound(), SCIPvarUpdateBestRootSol(), treeAddPendingBdchg(), updateImplicationGraphSOS1(), updateStatistics(), and updateWeightsTCliquegraph().
|
static |
Definition at line 36 of file GomoryHuTree.cpp.
Referenced by init_maxflow(), and maxflow().