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. More...

	~LPRelaxationSER ()

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

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

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

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. More...

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. More...

void	generateProblem ()
	Generate the basic LP model. More...

bool	separate ()
	Perform all available separation algorithms. More...

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

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

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

Private Attributes
const double	m_eps
	epsilon for double operations More...

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

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. More...

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 73 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 206 of file LPRelaxationSER.h.

◆ ~LPRelaxationSER()

template<typename T >

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

inline

Definition at line 234 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 283 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 318 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 269 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 120 of file LPRelaxationSER.h.

◆ generateProblem()

template<typename T >

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

private

Generate the basic LP model.

Definition at line 248 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 376 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 402 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 489 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 440 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 332 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 91 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 77 of file LPRelaxationSER.h.

◆ m_G

template<typename T >

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

private

Definition at line 74 of file LPRelaxationSER.h.

◆ m_isTerminal

template<typename T >

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

private

Definition at line 75 of file LPRelaxationSER.h.

◆ m_lowerBounds

template<typename T >

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

private

Definition at line 82 of file LPRelaxationSER.h.

◆ m_matrix

template<typename T >

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

private

Definition at line 80 of file LPRelaxationSER.h.

◆ m_objective

template<typename T >

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

private

Definition at line 81 of file LPRelaxationSER.h.

◆ m_osiSolver

template<typename T >

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

private

Definition at line 79 of file LPRelaxationSER.h.

◆ m_separateCliqueSize

template<typename T >

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

private

Definition at line 86 of file LPRelaxationSER.h.

◆ m_separationStage

template<typename T >

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

private

Definition at line 88 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 76 of file LPRelaxationSER.h.

◆ m_upperBound

template<typename T >

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

private

Definition at line 85 of file LPRelaxationSER.h.

◆ m_upperBounds

template<typename T >

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

private

Definition at line 83 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

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

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

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