Class managing the component-based subtour elimination LP relaxation for the Steiner tree problem and its solving. More...

#include <ogdf/graphalg/steiner_tree/LPRelaxationSER.h>

Public Member Functions
	LPRelaxationSER (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, FullComponentWithExtraStore< T, double > &fullCompStore, T upperBound=0, int cliqueSize=0, double eps=1e-8)
	Initialize the LP.

	~LPRelaxationSER ()

bool	solve ()
	Solve the LP. The solution will be written to the extra data of the full component store.

Private Member Functions
bool	addSubsetCoverConstraint (const ArrayBuffer< node > &subset)
	Add subset cover constraints to the LP for a given subset of terminals.

void	addTerminalCoverConstraint ()
	Add terminal cover constraints to the LP.

void	addYConstraint (const node t)
	Add constraint that the sum of x_C over all components C spanning terminal `t` is at least 1 to ensure y_t >= 0.

double	generateMinCutSeparationGraph (const ArrayBuffer< int > &activeComponents, node &source, node &target, GraphCopy &G, EdgeArray< double > &capacity, int &cutsFound)
	Generates an auxiliary multi-graph for separation (during LP solving): directed, with special source and target, without Steiner vertices of degree 2.

void	generateProblem ()
	Generate the basic LP model.

bool	separate ()
	Perform all available separation algorithms.

bool	separateConnected (const ArrayBuffer< int > &activeComponents)
	Separate to ensure that the solution is connected.

bool	separateCycles (const ArrayBuffer< int > &activeComponents)
	Perform the separation algorithm for cycle constraints (to obtain stronger LP solution)

bool	separateMinCut (const ArrayBuffer< int > &activeComponents)
	Perform the general cut-based separation algorithm.

Private Attributes
const double	m_eps
	epsilon for double operations

FullComponentWithExtraStore< T, double > &	m_fullCompStore
	all enumerated full components, with solution

const EdgeWeightedGraph< T > &	m_G

const NodeArray< bool > &	m_isTerminal

double *	m_lowerBounds

CoinPackedMatrix *	m_matrix

double *	m_objective

OsiSolverInterface *	m_osiSolver

const int	m_separateCliqueSize

int	m_separationStage

const List< node > &	m_terminals
	List of terminals.

const T	m_upperBound

double *	m_upperBounds

Detailed Description

template<typename T>
class ogdf::steiner_tree::LPRelaxationSER< T >

Class managing the component-based subtour elimination LP relaxation for the Steiner tree problem and its solving.

Definition at line 52 of file LPRelaxationSER.h.

Constructor & Destructor Documentation

◆ LPRelaxationSER()

template<typename T >

ogdf::steiner_tree::LPRelaxationSER< T >::LPRelaxationSER	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal,
		FullComponentWithExtraStore< T, double > &	fullCompStore,
		T	upperBound = `0`,
		int	cliqueSize = `0`,
		double	eps = `1e-8`
	)

inline

Initialize the LP.

Parameters

G	edge-weighted input graph
terminals	terminals of the Steiner instance
isTerminal	incidence vector of terminals
fullCompStore	the set of full components variables should be constructed for, augmented with extra for solution value
upperBound	an upper bound to be applied during the LP solving (or 0 if no upper bound should be applied)
cliqueSize	the maximal clique size for stronger LP constraints (or 0 if the original LP should be solved)
eps	epsilon used for comparisons

Definition at line 185 of file LPRelaxationSER.h.

◆ ~LPRelaxationSER()

template<typename T >

ogdf::steiner_tree::LPRelaxationSER< T >::~LPRelaxationSER ( )

inline

Definition at line 213 of file LPRelaxationSER.h.

Member Function Documentation

◆ addSubsetCoverConstraint()

template<typename T >

bool ogdf::steiner_tree::LPRelaxationSER< T >::addSubsetCoverConstraint ( const ArrayBuffer< node > & subset )

private

Add subset cover constraints to the LP for a given subset of terminals.

Definition at line 262 of file LPRelaxationSER.h.

◆ addTerminalCoverConstraint()

template<typename T >

void ogdf::steiner_tree::LPRelaxationSER< T >::addTerminalCoverConstraint ( )

private

Add terminal cover constraints to the LP.

Definition at line 297 of file LPRelaxationSER.h.

◆ addYConstraint()

template<typename T >

void ogdf::steiner_tree::LPRelaxationSER< T >::addYConstraint ( const node t )

private

Add constraint that the sum of x_C over all components C spanning terminal t is at least 1 to ensure y_t >= 0.

Definition at line 248 of file LPRelaxationSER.h.

◆ generateMinCutSeparationGraph()

template<typename T >

double ogdf::steiner_tree::LPRelaxationSER< T >::generateMinCutSeparationGraph	(	const ArrayBuffer< int > &	activeComponents,
		node &	source,
		node &	target,
		GraphCopy &	G,
		EdgeArray< double > &	capacity,
		int &	cutsFound
	)

inlineprivate

Generates an auxiliary multi-graph for separation (during LP solving): directed, with special source and target, without Steiner vertices of degree 2.

Definition at line 99 of file LPRelaxationSER.h.

◆ generateProblem()

template<typename T >

void ogdf::steiner_tree::LPRelaxationSER< T >::generateProblem ( )

private

Generate the basic LP model.

Definition at line 227 of file LPRelaxationSER.h.

◆ separate()

template<typename T >

bool ogdf::steiner_tree::LPRelaxationSER< T >::separate ( )

private

Perform all available separation algorithms.

Returns: True iff new constraints have been introduced

Definition at line 355 of file LPRelaxationSER.h.

◆ separateConnected()

template<typename T >

bool ogdf::steiner_tree::LPRelaxationSER< T >::separateConnected ( const ArrayBuffer< int > & activeComponents )

private

Separate to ensure that the solution is connected.

Returns: True iff new constraints have been introduced

Definition at line 381 of file LPRelaxationSER.h.

◆ separateCycles()

template<typename T >

bool ogdf::steiner_tree::LPRelaxationSER< T >::separateCycles ( const ArrayBuffer< int > & activeComponents )

private

Perform the separation algorithm for cycle constraints (to obtain stronger LP solution)

Returns: True iff new constraints have been introduced

Definition at line 468 of file LPRelaxationSER.h.

◆ separateMinCut()

template<typename T >

bool ogdf::steiner_tree::LPRelaxationSER< T >::separateMinCut ( const ArrayBuffer< int > & activeComponents )

private

Perform the general cut-based separation algorithm.

Returns: True iff new constraints have been introduced

Definition at line 419 of file LPRelaxationSER.h.

◆ solve()

template<typename T >

bool ogdf::steiner_tree::LPRelaxationSER< T >::solve ( )

Solve the LP. The solution will be written to the extra data of the full component store.

Returns: true iff it has found a solution (always true if given upper bound is zero)

Definition at line 311 of file LPRelaxationSER.h.

Member Data Documentation

◆ m_eps

template<typename T >

const double ogdf::steiner_tree::LPRelaxationSER< T >::m_eps

private

epsilon for double operations

Definition at line 70 of file LPRelaxationSER.h.

◆ m_fullCompStore

template<typename T >

FullComponentWithExtraStore<T, double>& ogdf::steiner_tree::LPRelaxationSER< T >::m_fullCompStore

private

all enumerated full components, with solution

Definition at line 56 of file LPRelaxationSER.h.

◆ m_G

template<typename T >

const EdgeWeightedGraph<T>& ogdf::steiner_tree::LPRelaxationSER< T >::m_G

private

Definition at line 53 of file LPRelaxationSER.h.

◆ m_isTerminal

template<typename T >

const NodeArray<bool>& ogdf::steiner_tree::LPRelaxationSER< T >::m_isTerminal

private

Definition at line 54 of file LPRelaxationSER.h.

◆ m_lowerBounds

template<typename T >

double* ogdf::steiner_tree::LPRelaxationSER< T >::m_lowerBounds

private

Definition at line 61 of file LPRelaxationSER.h.

◆ m_matrix

template<typename T >

CoinPackedMatrix* ogdf::steiner_tree::LPRelaxationSER< T >::m_matrix

private

Definition at line 59 of file LPRelaxationSER.h.

◆ m_objective

template<typename T >

double* ogdf::steiner_tree::LPRelaxationSER< T >::m_objective

private

Definition at line 60 of file LPRelaxationSER.h.

◆ m_osiSolver

template<typename T >

OsiSolverInterface* ogdf::steiner_tree::LPRelaxationSER< T >::m_osiSolver

private

Definition at line 58 of file LPRelaxationSER.h.

◆ m_separateCliqueSize

template<typename T >

const int ogdf::steiner_tree::LPRelaxationSER< T >::m_separateCliqueSize

private

Definition at line 65 of file LPRelaxationSER.h.

◆ m_separationStage

template<typename T >

int ogdf::steiner_tree::LPRelaxationSER< T >::m_separationStage

private

Definition at line 67 of file LPRelaxationSER.h.

◆ m_terminals

template<typename T >

const List<node>& ogdf::steiner_tree::LPRelaxationSER< T >::m_terminals

private

List of terminals.

Definition at line 55 of file LPRelaxationSER.h.

◆ m_upperBound

template<typename T >

const T ogdf::steiner_tree::LPRelaxationSER< T >::m_upperBound

private

Definition at line 64 of file LPRelaxationSER.h.

◆ m_upperBounds

template<typename T >

double* ogdf::steiner_tree::LPRelaxationSER< T >::m_upperBounds

private

Definition at line 62 of file LPRelaxationSER.h.

The documentation for this class was generated from the following file:

include/ogdf/graphalg/steiner_tree/LPRelaxationSER.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ LPRelaxationSER()

◆ ~LPRelaxationSER()

Member Function Documentation

◆ addSubsetCoverConstraint()

◆ addTerminalCoverConstraint()

◆ addYConstraint()

◆ generateMinCutSeparationGraph()

◆ generateProblem()

◆ separate()

◆ separateConnected()

◆ separateCycles()

◆ separateMinCut()

◆ solve()

Member Data Documentation

◆ m_eps

◆ m_fullCompStore

◆ m_G

◆ m_isTerminal

◆ m_lowerBounds

◆ m_matrix

◆ m_objective

◆ m_osiSolver

◆ m_separateCliqueSize

◆ m_separationStage

◆ m_terminals

◆ m_upperBound

◆ m_upperBounds

Open
Graph Drawing
Framework