Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree::LPRelaxationSER< T > Class Template Reference

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 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,
upperBound = 0,
int  cliqueSize = 0,
double  eps = 1e-8 
)
inline

Initialize the LP.

Parameters
Gedge-weighted input graph
terminalsterminals of the Steiner instance
isTerminalincidence vector of terminals
fullCompStorethe set of full components variables should be constructed for, augmented with extra for solution value
upperBoundan upper bound to be applied during the LP solving (or 0 if no upper bound should be applied)
cliqueSizethe maximal clique size for stronger LP constraints (or 0 if the original LP should be solved)
epsepsilon used for comparisons

Definition at line 191 of file LPRelaxationSER.h.

◆ ~LPRelaxationSER()

template<typename T >
ogdf::steiner_tree::LPRelaxationSER< T >::~LPRelaxationSER ( )
inline

Definition at line 220 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 275 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 314 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 259 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 100 of file LPRelaxationSER.h.

◆ generateProblem()

template<typename T >
void ogdf::steiner_tree::LPRelaxationSER< T >::generateProblem
private

Generate the basic LP model.

Definition at line 236 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 374 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 492 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 442 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 330 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 71 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 57 of file LPRelaxationSER.h.

◆ m_G

template<typename T >
const EdgeWeightedGraph<T>& ogdf::steiner_tree::LPRelaxationSER< T >::m_G
private

Definition at line 54 of file LPRelaxationSER.h.

◆ m_isTerminal

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

Definition at line 55 of file LPRelaxationSER.h.

◆ m_lowerBounds

template<typename T >
double* ogdf::steiner_tree::LPRelaxationSER< T >::m_lowerBounds
private

Definition at line 62 of file LPRelaxationSER.h.

◆ m_matrix

template<typename T >
CoinPackedMatrix* ogdf::steiner_tree::LPRelaxationSER< T >::m_matrix
private

Definition at line 60 of file LPRelaxationSER.h.

◆ m_objective

template<typename T >
double* ogdf::steiner_tree::LPRelaxationSER< T >::m_objective
private

Definition at line 61 of file LPRelaxationSER.h.

◆ m_osiSolver

template<typename T >
OsiSolverInterface* ogdf::steiner_tree::LPRelaxationSER< T >::m_osiSolver
private

Definition at line 59 of file LPRelaxationSER.h.

◆ m_separateCliqueSize

template<typename T >
const int ogdf::steiner_tree::LPRelaxationSER< T >::m_separateCliqueSize
private

Definition at line 66 of file LPRelaxationSER.h.

◆ m_separationStage

template<typename T >
int ogdf::steiner_tree::LPRelaxationSER< T >::m_separationStage
private

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

◆ m_upperBound

template<typename T >
const T ogdf::steiner_tree::LPRelaxationSER< T >::m_upperBound
private

Definition at line 65 of file LPRelaxationSER.h.

◆ m_upperBounds

template<typename T >
double* ogdf::steiner_tree::LPRelaxationSER< T >::m_upperBounds
private

Definition at line 63 of file LPRelaxationSER.h.


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