tpl_multicommodity.H File Reference

Multi-commodity flow algorithms. More...

#include <vector>
#include <limits>
#include <chrono>
#include <tpl_agraph.H>
#include <tpl_dynMapTree.H>
#include <Simplex.H>
#include <ah-errors.H>

Include dependency graph for tpl_multicommodity.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Commodity< Node, Flow_Type >
	Commodity definition for multi-commodity flow. More...
struct	Aleph::MCF_Arc< Arc_Info, FT >
	Arc information for multi-commodity flow. More...
class	Aleph::MCF_Graph< NodeT, ArcT >
	Multi-commodity flow network (directed graph). More...
struct	Aleph::MCF_Result< Flow_Type >
	Multi-commodity flow result. More...
class	Aleph::MCF_LP_Solver< Net >
	Multi-commodity flow solver using LP formulation. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class Net >
MCF_Result< typename Net::Flow_Type >	Aleph::solve_multicommodity_flow (Net &net)
	Solve multi-commodity flow problem.

Detailed Description

Multi-commodity flow algorithms.

This file provides data structures and algorithms for solving multi-commodity flow problems on capacitated networks.

Overview

In a multi-commodity flow problem, multiple commodities (types of flow) share the same network infrastructure. Each commodity has its own source-sink pair and demand, but all commodities compete for the shared arc capacities.

Problem Formulation

Given:

• Network G = (V, E) with arc capacities u_ij
• K commodities, each with source s_k, sink t_k, demand d_k, cost c_ij^k

Minimize: Σ_k Σ_{(i,j)} c_ij^k * x_ij^k

Subject to:

• Flow conservation: Σ_j x_ij^k - Σ_j x_ji^k = b_i^k ∀i,k
• Capacity sharing: Σ_k x_ij^k ≤ u_ij ∀(i,j)
• Non-negativity: x_ij^k ≥ 0 ∀(i,j),k

Where b_i^k = d_k if i=s_k, -d_k if i=t_k, 0 otherwise.

Algorithms

• LP Direct: Formulate as linear program and solve with Simplex
• Path-based: Generate paths and solve restricted LP (future)

Complexity

The LP formulation has O(K*E) variables and O(K*V + E) constraints. Solution time depends on the LP solver used.

Example: Two-commodity flow network

using GT = List_Graph<Graph_Node<string>, Graph_Arc<int>>;
GT network;
 
auto s1 = network.insert_node("Source1");
auto s2 = network.insert_node("Source2");
auto t1 = network.insert_node("Sink1");
auto t2 = network.insert_node("Sink2");
auto hub = network.insert_node("Hub");
 
// Shared infrastructure with capacity constraints
network.insert_arc(s1, hub, 100);  // capacity 100
network.insert_arc(s2, hub, 80);
network.insert_arc(hub, t1, 90);
network.insert_arc(hub, t2, 70);
 
// Commodity 1: s1 -> t1, demand 60
// Commodity 2: s2 -> t2, demand 50
// Both share hub's capacity

Example: Telecommunications network

// Multiple data streams sharing network links
// Each commodity = different data stream with source/dest
// Arcs = network links with bandwidth capacity
// Goal: maximize total throughput while respecting capacities

Author

Leandro Rabindranath León

Definition in file tpl_multicommodity.H.