SCIP
Solving Constraint Integer Programs
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) |
| 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 |
Macro Definition Documentation
◆ EPS
| #define EPS 1.0E-10 |
Definition at line 31 of file GomoryHuTree.cpp.
Referenced by global_relabel(), and maxflow().
Function Documentation
◆ create_graph()
Definition at line 38 of file GomoryHuTree.cpp.
References BMSallocMemory, BMSallocMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, FALSE, NULL, and TRUE.
Referenced by copy_graph(), and SCIP_DECL_READERREAD().
◆ free_graph()
|
static |
Definition at line 68 of file GomoryHuTree.cpp.
References BMSfreeMemory, and NULL.
Referenced by release_graph().
◆ capture_graph()
| void capture_graph | ( | GRAPH * | gr | ) |
Definition at line 78 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 | ) |
Definition at line 84 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()
| 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().
◆ fini_maxflow()
| void fini_maxflow | ( | ) |
◆ global_relabel()
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, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.
Referenced by maxflow().
◆ 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, GraphEdge::next, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.
Referenced by ghc_tree().
◆ nodeOnRootPath()
Definition at line 500 of file GomoryHuTree.cpp.
Referenced by constructCutList().
◆ constructCutList()
Definition at line 513 of file GomoryHuTree.cpp.
References FALSE, and nodeOnRootPath().
Referenced by ghc_tree().
◆ constructSingleCut()
◆ ghc_tree()
Definition at line 538 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 33 of file GomoryHuTree.cpp.
Referenced by alnsIncludeNeighborhood(), doTableCreate(), dualascent_init(), global_relabel(), is_active(), SCIP_DECL_DIALOGEXEC(), SCIP_DECL_SORTPTRCOMP(), SCIPcount(), SCIPdispAutoActivate(), SCIPincludeNonlinconsUpgrade(), SCIPincludeQuadconsUpgrade(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPvarGetProbvarBinary(), and setupProblem().
◆ number
|
static |
Definition at line 34 of file GomoryHuTree.cpp.
Referenced by computeSteinerTreeVnoi(), exprParse(), fini_maxflow(), getNJobs(), getNodeNumber(), getNResources(), global_relabel(), init_maxflow(), maxflow(), mpsinputReadLine(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_SORTPTRCOMP().
◆ max_dist
|
static |
Definition at line 35 of file GomoryHuTree.cpp.
Referenced by global_relabel(), and maxflow().
◆ bound
|
static |
Definition at line 35 of file GomoryHuTree.cpp.
Referenced by addBdchg(), addCoef(), analyzeGenVBoundConflict(), applyVboundsFixings(), checkRedundancy(), computePertubedSol(), conflictAddConflictCons(), consdataComputePseudoActivity(), consdataCreate(), consdataInvalidateActivities(), consdataRecomputeGlbMinactivity(), consdataRecomputeMaxactivity(), consdataRecomputeMinactivity(), convertBoundToInt(), createVarboundCons(), detectImpliedBounds(), determineBound(), filterExistingLP(), getDiveBdChgsSOS1conflictgraph(), getDiveBdChgsSOS1constraints(), getGenVBoundsMinActivity(), getGenVBoundsMinActivityConflict(), global_relabel(), impliesVlbPrecedenceCondition(), isBoundchgUseless(), maxflow(), nodeGetSolvalBinaryBigMSOS1(), optimize(), performDualfix(), presolRoundIndicator(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), removeFixedVariables(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_DIALOGEXEC(), SCIPapplyHeurDualval(), SCIPlpIsInfeasibilityProved(), SCIPvarGetConflictingBdchgDepth(), SCIPvarGetProbvarBound(), SCIPvarUpdateBestRootSol(), treeAddPendingBdchg(), updateImplicationGraphSOS1(), updateStatistics(), and updateWeightsTCliquegraph().
◆ co_check
|
static |
Definition at line 36 of file GomoryHuTree.cpp.
Referenced by init_maxflow(), and maxflow().