MinSteinerTreeDirectedCut.h File Reference

Classes for solving the Steiner tree problem exactly with a branch&cut algorithm. More...

#include <ogdf/basic/Array.h>
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Logger.h>
#include <ogdf/basic/Stopwatch.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/exceptions.h>
#include <ogdf/graphalg/MaxFlowGoldbergTarjan.h>
#include <ogdf/graphalg/MaxFlowModule.h>
#include <ogdf/graphalg/MinSTCutMaxFlow.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/MinSteinerTreeTakahashi.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraph.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
#include <ogdf/external/abacus.h>
#include <ogdf/lib/abacus/opensub.h>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <memory>

Go to the source code of this file.

Classes
class	ogdf::MinSteinerTreeDirectedCut< T >
	This class implements the Directed Cut Integer Linear Program for the Steiner tree problem. More...
class	ogdf::MinSteinerTreeDirectedCut< T >::DegreeConstraint
	Constraint for nodes, e.g., in/outdegree stuff. More...
class	ogdf::MinSteinerTreeDirectedCut< T >::DegreeEdgeConstraint
	Constraint for relating the indegree and one outgoing edge of a node. More...
class	ogdf::MinSteinerTreeDirectedCut< T >::DirectedCutConstraint
	Class for directed cuts (i.e., separated Steiner cuts) More...
class	ogdf::MinSteinerTreeDirectedCut< T >::EdgeConstraint
	Constraint for edges, e.g., subtour elimination constraints of size 2 ((G)SEC2) More...
class	ogdf::MinSteinerTreeDirectedCut< T >::EdgeVariable
	Variable for directed edges. More...
class	ogdf::MinSteinerTreeDirectedCut< T >::Master
	Master problem of Steiner tree branch&cut algorithm More...
class	ogdf::MinSteinerTreeDirectedCut< T >::Sub
	Subproblem of Steiner tree algorithm. More...

Namespaces
namespace	ogdf
	The namespace for all OGDF objects.

Detailed Description

Classes for solving the Steiner tree problem exactly with a branch&cut algorithm.

The used ILP formulation is the directed cut formulation.

The implementation follows the ideas from the literature, cf., e.g., T. Polzin, S. V. Daneshmand: "Improved algorithms for the Steiner problem in networks" or T. Koch, A. Martin: "Solving Steiner tree problems in graphs to optimality"

Author

Bernd Zey

License:

This file is part of the Open Graph Drawing Framework (OGDF).

Copyright (C)
See README.md in the OGDF root directory for details.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License Version 2 or 3 as published by the Free Software Foundation; see the file LICENSE.txt included in the packaging of this file for details.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, see http://www.gnu.org/copyleft/gpl.html

Definition in file MinSteinerTreeDirectedCut.h.