Multi-commodity flow solver using LP formulation. More...

#include <tpl_multicommodity.H>

Collaboration diagram for Aleph::MCF_LP_Solver< Net >:

Public Types
using	Node = typename Net::Node

using	Arc = typename Net::Arc

using	Flow_Type = typename Net::Flow_Type

using	Result = MCF_Result< Flow_Type >

Public Member Functions
	MCF_LP_Solver (Net &network)
	Construct solver for a network.

Result	solve ()
	Solve the multi-commodity flow problem.

void	print_formulation (size_t max_constraints=10) const
	Print LP formulation (for debugging).

Private Member Functions
size_t	var_index (size_t k, size_t arc_idx) const

Private Attributes
Net &	net

DynMapTree< Arc *, size_t >	arc_to_idx

Detailed Description

template<class Net>
class Aleph::MCF_LP_Solver< Net >

Multi-commodity flow solver using LP formulation.

Solves the MCF problem by formulating it as a linear program and using the Revised Simplex algorithm.

LP Formulation

Variables: x_{ij}^k for each arc (i,j) and commodity k Total: K * |E| variables

Constraints:

Flow conservation at each node for each commodity: K * |V|
Capacity constraints on each arc: |E|

Total constraints: K * |V| + |E|

Template Parameters

Net	Network type (should be MCF_Graph or compatible).

See also: MCF_Graph RevisedSimplex

Definition at line 442 of file tpl_multicommodity.H.

Member Typedef Documentation

◆ Arc

template<class Net >

using Aleph::MCF_LP_Solver< Net >::Arc = typename Net::Arc

Definition at line 446 of file tpl_multicommodity.H.

◆ Flow_Type

template<class Net >

using Aleph::MCF_LP_Solver< Net >::Flow_Type = typename Net::Flow_Type

Definition at line 447 of file tpl_multicommodity.H.

◆ Node

template<class Net >

using Aleph::MCF_LP_Solver< Net >::Node = typename Net::Node

Definition at line 445 of file tpl_multicommodity.H.

◆ Result

template<class Net >

using Aleph::MCF_LP_Solver< Net >::Result = MCF_Result<Flow_Type>

Definition at line 448 of file tpl_multicommodity.H.

Constructor & Destructor Documentation

◆ MCF_LP_Solver()

template<class Net >

Aleph::MCF_LP_Solver< Net >::MCF_LP_Solver ( Net & network )

inlineexplicit

Construct solver for a network.

Parameters

[in] network The multi-commodity network to solve.

Definition at line 465 of file tpl_multicommodity.H.

References Aleph::MCF_LP_Solver< Net >::arc_to_idx, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), and Aleph::MCF_LP_Solver< Net >::net.

Member Function Documentation

◆ print_formulation()

template<class Net >

void Aleph::MCF_LP_Solver< Net >::print_formulation ( size_t max_constraints = 10 ) const

inline

Print LP formulation (for debugging).

Parameters

[in] max_constraints Maximum constraints to print.

Definition at line 645 of file tpl_multicommodity.H.

References GraphCommon< GT, Node, Arc >::esize(), Aleph::maps(), Aleph::MCF_LP_Solver< Net >::net, and GraphCommon< GT, Node, Arc >::vsize().

◆ solve()

template<class Net >

Result Aleph::MCF_LP_Solver< Net >::solve ( )

inline

Solve the multi-commodity flow problem.

Formulates and solves the LP using the standard Simplex algorithm. The problem is formulated with equality constraints for flow conservation and inequality constraints for capacity.