paal::ir Namespace Reference

Iterative Rounding namespace. More...

Namespaces
	detail
	Detail of Iterative Rounding namespace.

Classes
class	bounded_degree_mst
	The class for solving the Bounded Degree MST problem using Iterative Rounding. More...
struct	bdmst_round_condition
struct	bdmst_relax_condition
struct	bdmst_init
struct	bdmst_set_solution
class	bdmst_violation_checker
	Violations checker for the separation oracle in the bounded degree minimum spanning tree problem. More...
struct	ga_relax_condition
struct	ga_set_solution
class	ga_init
class	generalised_assignment
	The class for solving the Generalised Assignment problem using Iterative Rounding. More...
class	default_round_condition
	Default column rounding condition component. More...
class	round_condition_equals
	Column rounding component. Rounds a column if its value is equal to one of the template parameter values. More...
class	round_condition_equals< arg, args...>
	Column rounding component. Rounds a column if its value is equal to one of the template parameter values. More...
class	round_condition_equals<>
	Column rounding component. Rounds a column if its value is equal to one of the template parameter values. Edge case (no template parameter values). More...
class	round_condition_to_fun
	Column rounding component. Rounds a column if its value satisfies a fixed condition. The column is rounded to a value defined by a fixed function. More...
class	cond_bigger_equal_than
	Checks if a variable is greater or equal than a fixed bound. More...
struct	round_condition_greater_than_half
	Column rounding component. A variable is rounded up to 1, if it has value at least half in the solution. More...
struct	default_solve_lp_to_extreme_point
	Finds an extreme point solution to the LP. More...
struct	default_resolve_lp_to_extreme_point
	Finds an extreme point solution to the LP. More...
class	default_stop_condition
	Default stop condition component. More...
class	relaxations_limit_condition
	Checks if the relaxations limit was reached. More...
struct	trivial_visitor
	Default Iterative Rounding visitor. More...
class	default_solve_lp_in_row_generation
struct	row_generation_solve_lp
class	min_cut_finder
	Class for creating and modifying directed graphs with edge capacities and finding directed minimum cuts between given vertices. More...
class	steiner_network
	The class for solving the Steiner Network problem using Iterative Rounding. More...
struct	steiner_network_init
struct	steiner_network_round_condition
struct	steiner_network_set_solution
class	steiner_network_violation_checker
	Violations checker for the separation oracle in the steiner network problem. More...
class	steiner_component
	Class represents k-components of Steiner Tree. Component is a subtree whose terminals coincide with leaves. More...
class	steiner_components
class	steiner_tree_all_generator
class	steiner_tree_graph_all_generator
class	steiner_tree_random_generator
class	steiner_tree_smart_generator
class	steiner_tree
	The class for solving the Steiner Tree problem using Iterative Rounding. More...
struct	steiner_tree_init
class	steiner_tree_round_condition
struct	steiner_tree_stop_condition
struct	steiner_tree_set_solution
class	steiner_tree_violation_checker
	Violations checker for the separation oracle in the steiner tree problem. More...
class	steiner_utils
struct	ta_round_condition
struct	ta_set_solution
class	ta_init
class	tree_aug
	This is Jain's iterative rounding 2-approximation algorithm for the Generalised Steiner Network Problem, specialized for the Tree Augmentation Problem. More...

Typedefs
template<typename Init = bdmst_init, typename RoundCondition = bdmst_round_condition, typename RelaxContition = bdmst_relax_condition, typename SetSolution = bdmst_set_solution, typename SolveLPToExtremePoint = ir::row_generation_solve_lp<>, typename ResolveLpToExtremePoint = ir::row_generation_solve_lp<>>
using	bdmst_ir_components = IRcomponents< Init, RoundCondition, RelaxContition, SetSolution, SolveLPToExtremePoint, ResolveLpToExtremePoint >
template<typename Init = ga_init, typename RoundCondition = default_round_condition, typename RelaxContition = ga_relax_condition, typename SetSolution = ga_set_solution>
using	ga_ir_components = IRcomponents< Init, RoundCondition, RelaxContition, SetSolution >
using	components = data_structures::components< Init, data_structures::NameWithDefault< RoundCondition, default_round_condition >, data_structures::NameWithDefault< RelaxCondition, utils::always_false >, data_structures::NameWithDefault< SetSolution, utils::skip_functor >, data_structures::NameWithDefault< SolveLP, default_solve_lp_to_extreme_point >, data_structures::NameWithDefault< ResolveLP, default_resolve_lp_to_extreme_point >, data_structures::NameWithDefault< StopCondition, default_stop_condition >, data_structures::NameWithDefault< RelaxationsLimit, utils::always_false >>
template<typename... Args>
using	IRcomponents = typename components::type< Args...>
	Iterative rounding components.
using	IRSolutionCost = boost::optional< double >
	Iterative Rounding solution cost type. Solution cost only makes sense if the LP has been solved to optimal value.
using	IRResult = std::pair< lp::problem_type, IRSolutionCost >
template<typename Init = steiner_network_init, typename RoundCondition = steiner_network_round_condition, typename RelaxContition = utils::always_false, typename SetSolution = steiner_network_set_solution, typename SolveLPToExtremePoint = row_generation_solve_lp<>, typename ResolveLPToExtremePoint = row_generation_solve_lp<>>
using	steiner_network_ir_components = IRcomponents< Init, RoundCondition, RelaxContition, SetSolution, SolveLPToExtremePoint, ResolveLPToExtremePoint >
template<typename Init = steiner_tree_init, typename RoundCondition = steiner_tree_round_condition, typename RelaxCondition = utils::always_false, typename SetSolution = steiner_tree_set_solution, typename SolveLPToExtremePoint = row_generation_solve_lp<>, typename ResolveLPToExtremePoint = row_generation_solve_lp<>, typename StopCondition = steiner_tree_stop_condition>
using	steiner_tree_ir_components = IRcomponents< Init, RoundCondition, RelaxCondition, SetSolution, SolveLPToExtremePoint, ResolveLPToExtremePoint, StopCondition >
template<typename Init = ta_init, typename RoundCondition = ta_round_condition, typename RelaxContition = utils::always_false, typename SetSolution = ta_set_solution>
using	tree_augmentation_ir_components = IRcomponents< Init, RoundCondition, RelaxContition, SetSolution >

Functions
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator , typename P , typename T , typename R >
auto	make_bounded_degree_mst (const Graph &g, const DegreeBounds &deg_bounds, const boost::bgl_named_params< P, T, R > &params, SpanningTreeOutputIterator result_spanning_tree, Oracle oracle=Oracle()) -> bounded_degree_mst< Graph, DegreeBounds, decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), SpanningTreeOutputIterator, Oracle >
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator >
auto	make_bounded_degree_mst (const Graph &g, const DegreeBounds &deg_bounds, SpanningTreeOutputIterator result_spanning_tree, Oracle oracle=Oracle()) -> decltype(make_bounded_degree_mst(g, deg_bounds, boost::no_named_parameters(), result_spanning_tree, oracle))
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator , typename IRcomponents = bdmst_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >
IRResult	bounded_degree_mst_iterative_rounding (const Graph &g, const DegreeBounds &deg_bounds, const boost::bgl_named_params< P, T, R > &params, SpanningTreeOutputIterator result_spanning_tree, IRcomponents components=IRcomponents(), Oracle oracle=Oracle(), Visitor visitor=Visitor())
	Solves the Bounded Degree MST problem using Iterative Rounding. Named version. More...
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator , typename IRcomponents = bdmst_ir_components<>, typename Visitor = trivial_visitor>
IRResult	bounded_degree_mst_iterative_rounding (const Graph &g, const DegreeBounds &deg_bounds, SpanningTreeOutputIterator result_spanning_tree, IRcomponents components=IRcomponents(), Oracle oracle=Oracle(), Visitor visitor=Visitor())
	Solves the Bounded Degree MST problem using Iterative Rounding. All default parameters. More...
template<typename MachineIter , typename JobIter , typename Cost , typename ProceedingTime , typename MachineAvailableTime , typename JobsToMachinesOutputIterator >
generalised_assignment < MachineIter, JobIter, Cost, ProceedingTime, MachineAvailableTime, JobsToMachinesOutputIterator >	make_generalised_assignment (MachineIter mbegin, MachineIter mend, JobIter jbegin, JobIter jend, const Cost &c, const ProceedingTime &t, const MachineAvailableTime &T, JobsToMachinesOutputIterator jobs_to_machines)
	Creates a generalised_assignment object. More...
template<typename MachineIter , typename JobIter , typename Cost , typename ProceedingTime , typename MachineAvailableTime , typename JobsToMachinesOutputIterator , typename Components = ga_ir_components<>, typename Visitor = trivial_visitor>
IRResult	generalised_assignment_iterative_rounding (MachineIter mbegin, MachineIter mend, JobIter jbegin, JobIter jend, const Cost &c, const ProceedingTime &t, const MachineAvailableTime &T, JobsToMachinesOutputIterator jobs_to_machines, Components components=Components(), Visitor visitor=Visitor())
	Solves the Generalised Assignment problem using Iterative Rounding. More...
template<typename... Args>
auto	make_IRcomponents (Args &&...args) -> decltype(components::make_components(std::forward< Args >(args)...))
	Returns iterative rounding components.
template<typename Problem , typename IRcomponents , typename Visitor = trivial_visitor, typename LP = lp::glp>
IRResult	solve_iterative_rounding (Problem &problem, IRcomponents components, Visitor visitor=Visitor())
	Solves an Iterative Rounding problem. More...
template<typename Problem , typename IRcomponents , typename Visitor = trivial_visitor, typename LP = lp::glp>
IRResult	solve_dependent_iterative_rounding (Problem &problem, IRcomponents components, Visitor visitor=Visitor())
	Solves an Iterative Rounding problem with dependent rounding. More...
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator , typename P , typename T , typename R >
auto	make_steiner_network (const Graph &g, const Restrictions &restrictions, const boost::bgl_named_params< P, T, R > &params, ResultNetworkOutputIterator result_network, Oracle oracle=Oracle()) -> steiner_network< Graph, Restrictions, decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), ResultNetworkOutputIterator, Oracle >
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator >
auto	make_steiner_network (const Graph &g, const Restrictions &restrictions, ResultNetworkOutputIterator result_network, Oracle oracle=Oracle()) -> decltype(make_steiner_network(g, restrictions, boost::no_named_parameters(), result_network, oracle))
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator , typename IRcomponents = steiner_network_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >
IRResult	steiner_network_iterative_rounding (const Graph &g, const Restrictions &restrictions, const boost::bgl_named_params< P, T, R > &params, ResultNetworkOutputIterator result, IRcomponents components=IRcomponents(), Oracle oracle=Oracle(), Visitor visitor=Visitor())
	Solves the Steiner Network problem using Iterative Rounding. Named version. More...
template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator , typename IRcomponents = steiner_network_ir_components<>, typename Visitor = trivial_visitor>
IRResult	steiner_network_iterative_rounding (const Graph &g, const Restrictions &restrictions, ResultNetworkOutputIterator result, IRcomponents components=IRcomponents(), Oracle oracle=Oracle(), Visitor visitor=Visitor())
	Solves the Steiner Network problem using Iterative Rounding. All default parameters. More...
template<typename Vertex , typename Graph , typename Terminals >
steiner_tree_graph_all_generator < Graph, Vertex, Terminals >	make_steiner_tree_graph_all_generator (const Graph &graph, const Terminals &terminals, int K=4)
template<typename Oracle = lp::random_violated_separation_oracle, typename OrigMetric , typename Terminals , typename Result , typename Strategy >
steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >	make_steiner_tree (const OrigMetric &metric, const Terminals &terminals, const Terminals &steiner_vertices, Result result, const Strategy &strategy, Oracle oracle=Oracle())
template<typename Oracle = lp::random_violated_separation_oracle, typename Strategy = steiner_tree_all_generator, typename OrigMetric , typename Terminals , typename Result , typename IRcomponents = steiner_tree_ir_components<>, typename Visitor = trivial_visitor>
lp::problem_type	steiner_tree_iterative_rounding (const OrigMetric &metric, const Terminals &terminals, const Terminals &steiner_vertices, Result result, Strategy strategy=Strategy{}, IRcomponents comps=IRcomponents{}, Oracle oracle=Oracle{}, Visitor visitor=Visitor{})
	Solves the Steiner Tree problem using Iterative Rounding.
template<typename Graph , typename EdgeSetOutputIterator , typename P , typename T , typename R >
auto	make_tree_aug (const Graph &g, const boost::bgl_named_params< P, T, R > &params, EdgeSetOutputIterator solution) -> tree_aug< Graph, decltype(choose_const_pmap(get_param(params, boost::edge_color), g, boost::edge_color)), decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), EdgeSetOutputIterator >
template<typename Graph , typename EdgeSetOutputIterator >
auto	make_tree_aug (const Graph &g, EdgeSetOutputIterator solution) -> decltype(make_tree_aug(g, boost::no_named_parameters(), solution))
template<typename Graph , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >
IRResult	tree_augmentation_iterative_rounding (const Graph &g, const boost::bgl_named_params< P, T, R > &params, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
	Solves the Tree Augmentation problem using Iterative Rounding. Named parameters. More...
template<typename Graph , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor>
IRResult	tree_augmentation_iterative_rounding (const Graph &g, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
	Solves the Tree Augmentation problem using Iterative Rounding. All default parameters. More...

Detailed Description

Iterative Rounding namespace.

Typedef Documentation

using paal::ir::IRResult = typedef std::pair<lp::problem_type, IRSolutionCost>

Iterative Rounding result type: Pair consisting of LP problem type and IR solution cost.

Definition at line 294 of file iterative_rounding.hpp.

Function Documentation

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator , typename IRcomponents = bdmst_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >

IRResult paal::ir::bounded_degree_mst_iterative_rounding	(	const Graph &	g,
		const DegreeBounds &	deg_bounds,
		const boost::bgl_named_params< P, T, R > &	params,
		SpanningTreeOutputIterator	result_spanning_tree,
		IRcomponents	components = IRcomponents(),
		Oracle	oracle = Oracle(),
		Visitor	visitor = Visitor()
	)

Solves the Bounded Degree MST problem using Iterative Rounding. Named version.

Template Parameters

Oracle
Graph
DegreeBounds
SpanningTreeOutputIterator
IRcomponents
Visitor
P
T
R

Parameters

g
deg_bounds
result_spanning_tree
params
components
oracle
visitor

Returns

solution status

Definition at line 582 of file bounded_degree_mst.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator , typename IRcomponents = bdmst_ir_components<>, typename Visitor = trivial_visitor>

IRResult paal::ir::bounded_degree_mst_iterative_rounding	(	const Graph &	g,
		const DegreeBounds &	deg_bounds,
		SpanningTreeOutputIterator	result_spanning_tree,
		IRcomponents	components = IRcomponents(),
		Oracle	oracle = Oracle(),
		Visitor	visitor = Visitor()
	)

Solves the Bounded Degree MST problem using Iterative Rounding. All default parameters.

Template Parameters

Oracle
Graph
DegreeBounds
SpanningTreeOutputIterator
IRcomponents
Visitor

Parameters

g
deg_bounds
result_spanning_tree
components
oracle
visitor

Returns

solution status

Definition at line 621 of file bounded_degree_mst.hpp.

template<typename MachineIter , typename JobIter , typename Cost , typename ProceedingTime , typename MachineAvailableTime , typename JobsToMachinesOutputIterator , typename Components = ga_ir_components<>, typename Visitor = trivial_visitor>

IRResult paal::ir::generalised_assignment_iterative_rounding	(	MachineIter	mbegin,
		MachineIter	mend,
		JobIter	jbegin,
		JobIter	jend,
		const Cost &	c,
		const ProceedingTime &	t,
		const MachineAvailableTime &	T,
		JobsToMachinesOutputIterator	jobs_to_machines,
		Components	components = Components(),
		Visitor	visitor = Visitor()
	)

Solves the Generalised Assignment problem using Iterative Rounding.

Template Parameters

MachineIter
JobIter
Cost
ProceedingTime
MachineAvailableTime
JobsToMachinesOutputIterator
Components
Visitor

Parameters

mbegin	begin machines iterator
mend	end machines iterator
jbegin	begin jobs iterator
jend	end jobs iterator
c	costs of assignments
t	jobs proceeding times
T	times available for the machines
jobs_to_machines	found assignment
components	IR components
visitor

Returns

solution status

Definition at line 363 of file generalised_assignment.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator , typename P , typename T , typename R >

auto paal::ir::make_bounded_degree_mst	(	const Graph &	g,
		const DegreeBounds &	deg_bounds,
		const boost::bgl_named_params< P, T, R > &	params,
		SpanningTreeOutputIterator	result_spanning_tree,
		Oracle	oracle = Oracle()
	)		-> bounded_degree_mst<Graph, DegreeBounds, decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), SpanningTreeOutputIterator, Oracle>

Creates a bounded_degree_mst object. Named version. The returned object can be used to check input validity or to get a lower bound on the optimal solution cost.

Template Parameters

Oracle
Graph
DegreeBounds
SpanningTreeOutputIterator
P
T
R

Parameters

g
deg_bounds
params
result_spanning_tree
oracle

Returns

bounded_degree_mst object

Definition at line 304 of file bounded_degree_mst.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename DegreeBounds , typename SpanningTreeOutputIterator >

auto paal::ir::make_bounded_degree_mst	(	const Graph &	g,
		const DegreeBounds &	deg_bounds,
		SpanningTreeOutputIterator	result_spanning_tree,
		Oracle	oracle = Oracle()
	)		-> decltype(make_bounded_degree_mst(g, deg_bounds, boost::no_named_parameters(), result_spanning_tree, oracle))

Creates a bounded_degree_mst object. All default parameters. The returned object can be used to check input validity or to get a lower bound on the optimal solution cost.

Template Parameters

Oracle
Graph
DegreeBounds
SpanningTreeOutputIterator

Parameters

g
deg_bounds
result_spanning_tree
oracle

Returns

bounded_degree_mst object

Definition at line 340 of file bounded_degree_mst.hpp.

template<typename MachineIter , typename JobIter , typename Cost , typename ProceedingTime , typename MachineAvailableTime , typename JobsToMachinesOutputIterator >

generalised_assignment<MachineIter, JobIter, Cost, ProceedingTime, MachineAvailableTime, JobsToMachinesOutputIterator> paal::ir::make_generalised_assignment	(	MachineIter	mbegin,
		MachineIter	mend,
		JobIter	jbegin,
		JobIter	jend,
		const Cost &	c,
		const ProceedingTime &	t,
		const MachineAvailableTime &	T,
		JobsToMachinesOutputIterator	jobs_to_machines
	)

Creates a generalised_assignment object.

Template Parameters

MachineIter
JobIter
Cost
ProceedingTime
MachineAvailableTime
JobsToMachinesOutputIterator

Parameters

mbegin	begin machines iterator
mend	end machines iterator
jbegin	begin jobs iterator
jend	end jobs iterator
c	costs of assignments
t	jobs proceeding times
T	times available for the machines
jobs_to_machines	found assignment

Returns

generalised_assignment object

Definition at line 323 of file generalised_assignment.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator , typename P , typename T , typename R >

auto paal::ir::make_steiner_network	(	const Graph &	g,
		const Restrictions &	restrictions,
		const boost::bgl_named_params< P, T, R > &	params,
		ResultNetworkOutputIterator	result_network,
		Oracle	oracle = Oracle()
	)		-> steiner_network<Graph, Restrictions, decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), ResultNetworkOutputIterator, Oracle>

Creates a steiner_network object. Named version. The returned object can be used to check input validity or to get a lower bound on the optimal solution cost.

Template Parameters

Oracle
Graph
Restrictions
ResultNetworkOutputIterator
P
T
R

Parameters

g
restrictions
params
result_network
oracle

Returns

steiner_network object

Definition at line 266 of file steiner_network.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator >

auto paal::ir::make_steiner_network	(	const Graph &	g,
		const Restrictions &	restrictions,
		ResultNetworkOutputIterator	result_network,
		Oracle	oracle = Oracle()
	)		-> decltype(make_steiner_network(g, restrictions, boost::no_named_parameters(), result_network, oracle))

Creates a steiner_network object. All default parameters. The returned object can be used to check input validity or to get a lower bound on the optimal solution cost.

Template Parameters

Oracle
Graph
Restrictions
ResultNetworkOutputIterator

Parameters

g
restrictions
result_network
oracle

Returns

steiner_network object

Definition at line 300 of file steiner_network.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename OrigMetric , typename Terminals , typename Result , typename Strategy >

steiner_tree<OrigMetric, Terminals, Result, Strategy, Oracle> paal::ir::make_steiner_tree	(	const OrigMetric &	metric,
		const Terminals &	terminals,
		const Terminals &	steiner_vertices,
		Result	result,
		const Strategy &	strategy,
		Oracle	oracle = Oracle()
	)

Makes steiner_tree object. Just to avoid providing type names in template.

Definition at line 333 of file steiner_tree.hpp.

template<typename Vertex , typename Graph , typename Terminals >

steiner_tree_graph_all_generator<Graph, Vertex, Terminals> paal::ir::make_steiner_tree_graph_all_generator	(	const Graph &	graph,
		const Terminals &	terminals,
		int	K = 4
	)

Makes a graph_all_generator object.

Definition at line 239 of file steiner_strategy.hpp.

template<typename Graph , typename EdgeSetOutputIterator , typename P , typename T , typename R >

auto paal::ir::make_tree_aug	(	const Graph &	g,
		const boost::bgl_named_params< P, T, R > &	params,
		EdgeSetOutputIterator	solution
	)		-> tree_aug< Graph, decltype(choose_const_pmap(get_param(params, boost::edge_color), g, boost::edge_color)), decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), EdgeSetOutputIterator>

Creates a tree_aug object. Named parameters. The returned object can be used to check input validity or to get a lower bound on the optimal solution cost.

Template Parameters

Graph
EdgeSetOutputIterator
P
T
R

Parameters

g
params
solution

Returns

tree_aug object

Definition at line 527 of file tree_augmentation.hpp.

template<typename Graph , typename EdgeSetOutputIterator >

auto paal::ir::make_tree_aug	(	const Graph &	g,
		EdgeSetOutputIterator	solution
	)		-> decltype(make_tree_aug(g, boost::no_named_parameters(), solution))

Creates a tree_aug object. All default parameters. The returned object can be used to check input validity or to get a lower bound on the optimal solution cost.

Template Parameters

Graph
EdgeSetOutputIterator

Parameters

g
solution

Returns

tree_aug object

Definition at line 563 of file tree_augmentation.hpp.

template<typename Problem , typename IRcomponents , typename Visitor = trivial_visitor, typename LP = lp::glp>

IRResult paal::ir::solve_dependent_iterative_rounding	(	Problem &	problem,
		IRcomponents	components,
		Visitor	visitor = Visitor()
	)

Solves an Iterative Rounding problem with dependent rounding.

Template Parameters

Problem
IRcomponents
Visitor
LP

Parameters

problem	IR problem
components	IR problem components
visitor	visitor object used for logging progress of the algoithm

Definition at line 342 of file iterative_rounding.hpp.

template<typename Problem , typename IRcomponents , typename Visitor = trivial_visitor, typename LP = lp::glp>

IRResult paal::ir::solve_iterative_rounding	(	Problem &	problem,
		IRcomponents	components,
		Visitor	visitor = Visitor()
	)

Solves an Iterative Rounding problem.

Template Parameters

Problem
IRcomponents
Visitor
LP

Parameters

problem	IR problem
components	IR problem components
visitor	visitor object used for logging progress of the algoithm

Definition at line 308 of file iterative_rounding.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator , typename IRcomponents = steiner_network_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >

IRResult paal::ir::steiner_network_iterative_rounding	(	const Graph &	g,
		const Restrictions &	restrictions,
		const boost::bgl_named_params< P, T, R > &	params,
		ResultNetworkOutputIterator	result,
		IRcomponents	components = IRcomponents(),
		Oracle	oracle = Oracle(),
		Visitor	visitor = Visitor()
	)

Solves the Steiner Network problem using Iterative Rounding. Named version.

Template Parameters

Oracle
Graph
Restrictions
ResultNetworkOutputIterator
IRcomponents
Visitor
P
T
R

Parameters

g
restrictions
params
result
components
oracle
visitor

Returns

solution status

Definition at line 483 of file steiner_network.hpp.

template<typename Oracle = lp::random_violated_separation_oracle, typename Graph , typename Restrictions , typename ResultNetworkOutputIterator , typename IRcomponents = steiner_network_ir_components<>, typename Visitor = trivial_visitor>

IRResult paal::ir::steiner_network_iterative_rounding	(	const Graph &	g,
		const Restrictions &	restrictions,
		ResultNetworkOutputIterator	result,
		IRcomponents	components = IRcomponents(),
		Oracle	oracle = Oracle(),
		Visitor	visitor = Visitor()
	)

Solves the Steiner Network problem using Iterative Rounding. All default parameters.

Template Parameters

Oracle
Graph
Restrictions
ResultNetworkOutputIterator
IRcomponents
Visitor

Parameters

g
restrictions
result
components
oracle
visitor

Returns

solution status

Definition at line 522 of file steiner_network.hpp.

template<typename Graph , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor, typename P , typename T , typename R >

IRResult paal::ir::tree_augmentation_iterative_rounding	(	const Graph &	g,
		const boost::bgl_named_params< P, T, R > &	params,
		EdgeSetOutputIterator	solution,
		IRcomponents	components = IRcomponents(),
		Visitor	visitor = Visitor()
	)

Solves the Tree Augmentation problem using Iterative Rounding. Named parameters.

Template Parameters

Graph
EdgeSetOutputIterator
IRcomponents
Visitor
P
T
R

Parameters

g
params
solution
components
visitor

Returns

solution status

Definition at line 591 of file tree_augmentation.hpp.

template<typename Graph , typename EdgeSetOutputIterator , typename IRcomponents = tree_augmentation_ir_components<>, typename Visitor = trivial_visitor>

IRResult paal::ir::tree_augmentation_iterative_rounding	(	const Graph &	g,
		EdgeSetOutputIterator	solution,
		IRcomponents	components = IRcomponents(),
		Visitor	visitor = Visitor()
	)

Solves the Tree Augmentation problem using Iterative Rounding. All default parameters.

Template Parameters

Graph
EdgeSetOutputIterator
IRcomponents
Visitor

Parameters

g
solution
components
visitor

Returns

solution status

Definition at line 623 of file tree_augmentation.hpp.