Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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.
 
 ~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
 
doublem_lowerBounds
 
CoinPackedMatrixm_matrix
 
doublem_objective
 
OsiSolverInterfacem_osiSolver
 
const int m_separateCliqueSize
 
int m_separationStage
 
const List< node > & m_terminals
 List of terminals.
 
constm_upperBound
 
doublem_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 185 of file LPRelaxationSER.h.

◆ ~LPRelaxationSER()

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

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: