All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Namespaces | Classes | Typedefs | Functions
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
mbeginbegin machines iterator
mendend machines iterator
jbeginbegin jobs iterator
jendend jobs iterator
ccosts of assignments
tjobs proceeding times
Ttimes available for the machines
jobs_to_machinesfound assignment
componentsIR 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
mbeginbegin machines iterator
mendend machines iterator
jbeginbegin jobs iterator
jendend jobs iterator
ccosts of assignments
tjobs proceeding times
Ttimes available for the machines
jobs_to_machinesfound 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
problemIR problem
componentsIR problem components
visitorvisitor 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
problemIR problem
componentsIR problem components
visitorvisitor 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.