SCIP

Solving Constraint Integer Programs

src

Detailed Description

generator for global cuts in undirected graphs

Author: Georg Skorobohatyj; Timo Berthold

Definition in file GomoryHuTree.h.

#include "objscip/objscip.h"

Include dependency graph for GomoryHuTree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef struct GraphNode	GRAPHNODE

typedef struct GraphEdge	GRAPHEDGE

typedef struct Graph	GRAPH

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

void	capture_graph (GRAPH *gr)

void	release_graph (GRAPH **gr)

SCIP_Bool	gmincut (GRAPH gr, double mincap, long *n_shore)

SCIP_Bool	ghc_tree (GRAPH gr, SCIP_Bool cuts, int ncuts, double minviol)

Typedef Documentation

typedef struct Graph GRAPH

typedef struct GraphEdge GRAPHEDGE

typedef struct GraphNode GRAPHNODE

Function Documentation

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

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

Definition at line 38 of file GomoryHuTree.cpp.

Referenced by copy_graph(), and SCIP_DECL_READERREAD().

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

Definition at line 536 of file GomoryHuTree.cpp.

References GraphNode::alive, constructCutList(), constructSingleCut(), fini_maxflow(), init_maxflow(), maxflow(), GraphNode::mincap, Graph::nnodes, Graph::nodes, and GraphNode::parent.

Referenced by sepaSubtour().

SCIP_Bool gmincut	(	GRAPH *	gr,
		double *	mincap,
		long *	n_shore
	)

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