Scippy

SCIP

Solving Constraint Integer Programs

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)

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

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

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 void free_graph ( GRAPH ** gr )

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

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

Definition at line 118 of file GomoryHuTree.cpp.

References number.

Referenced by ghc_tree().

◆ global_relabel()

void global_relabel	(	GRAPH *	gr,
		GRAPHNODE *	tptr
	)

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, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.

Referenced by maxflow().

◆ maxflow()

double maxflow	(	GRAPH *	gr,
		GRAPHNODE *	s_ptr,
		GRAPHNODE *	t_ptr
	)

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, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.

Referenced by ghc_tree().

◆ nodeOnRootPath()

SCIP_Bool nodeOnRootPath	(	GRAPH *	gr,
		int	i,
		int	j
	)

Definition at line 500 of file GomoryHuTree.cpp.

References FALSE, GraphNode::id, Graph::nodes, GraphNode::parent, and TRUE.

Referenced by constructCutList().

◆ constructCutList()

void constructCutList	(	GRAPH *	gr,
		SCIP_Bool **	cuts,
		int *	ncuts,
		double	minviol
	)

Definition at line 513 of file GomoryHuTree.cpp.

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

Referenced by ghc_tree().

◆ constructSingleCut()

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

Definition at line 531 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
	)

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().

Variable Documentation

◆ active

GRAPHNODE** active

static

Definition at line 33 of file GomoryHuTree.cpp.

Referenced by global_relabel(), SCIP_DECL_DIALOGEXEC(), SCIP_DECL_SORTPTRCOMP(), SCIPcount(), SCIPdispAutoActivate(), SCIPincludeNonlinconsUpgrade(), SCIPincludeQuadconsUpgrade(), SCIPvarGetProbvarBinary(), and setupProblem().

◆ number

long* number

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().

◆ max_dist

long max_dist

static

Definition at line 35 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

◆ bound

long bound

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_DIALOGEXEC(), SCIPapplyHeurDualval(), SCIPlpIsInfeasibilityProved(), SCIPlpiStrongbranch(), SCIPvarGetConflictingBdchgDepth(), SCIPvarGetProbvarBound(), SCIPvarUpdateBestRootSol(), SolveWSimplex(), treeAddPendingBdchg(), updateImplicationGraphSOS1(), updateStatistics(), and updateWeightsTCliquegraph().

◆ co_check

SCIP_Bool co_check

static

Definition at line 36 of file GomoryHuTree.cpp.

Referenced by init_maxflow(), and maxflow().