mincost_flow_example.cc File Reference

Minimum Cost Maximum Flow: Optimization with Cost Constraints. More...

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cstring>
#include <tpl_netcost.H>
#include <tpl_mincost.H>

Include dependency graph for mincost_flow_example.cc:

Go to the source code of this file.

Typedefs
using	Flow_Type = double
using	CostNet = Net_Cost_Graph< Net_Cost_Node< string >, Net_Cost_Arc< Empty_Class, Flow_Type > >
using	Node = CostNet::Node
using	Arc = CostNet::Arc

Functions
static void	usage (const char *prog)
static bool	has_flag (int argc, char *argv[], const char *flag)
static const char *	get_opt_value (int argc, char *argv[], const char *opt)
CostNet	build_simple_network ()
	Build a simple logistics network.
static void	demo_compare_algorithms_on_logistics ()
void	print_cost_network (CostNet &net, const string &title)
	Print network with flows and costs.
void	demo_assignment_problem ()
	Demonstrate the assignment problem.
void	demo_transportation_problem ()
	Demonstrate the transportation problem.
void	demo_mincost_maxflow ()
	Demonstrate min-cost max-flow.
int	main (int argc, char *argv[])

Detailed Description

Minimum Cost Maximum Flow: Optimization with Cost Constraints.

This example demonstrates the minimum cost flow problem, a fundamental optimization problem that combines maximum flow with cost minimization. Unlike basic max-flow (which only maximizes flow), min-cost max-flow finds the cheapest way to achieve maximum flow.

The Min-Cost Max-Flow Problem

Problem Statement

Given a directed network where each edge has:

• Capacity: Maximum flow allowed (c(e))
• Cost: Cost per unit of flow (w(e))

Find a flow that:

1. Maximizes total flow from source to sink
2. Minimizes total cost among all maximum flows

Mathematical Formulation

Minimize: Σ (flow(e) × cost(e)) for all edges e
 
Subject to:
  - Flow conservation: Σ flow into v = Σ flow out of v (for all v ≠ s,t)
  - Capacity constraints: 0 ≤ flow(e) ≤ capacity(e) for all edges e
  - Flow maximization: Total flow is maximum possible

Algorithms Demonstrated

1. Cycle Canceling Algorithm

Strategy: Start with max-flow, then reduce cost by canceling negative cycles

Algorithm:

1. Find any maximum flow (using Ford-Fulkerson, Dinic, etc.)
2. Build residual graph with costs:
   - Forward edge: cost = original cost
   - Backward edge: cost = -original cost (can "undo" flow)
3. While negative-cost cycle exists in residual graph:
   a. Find negative-cost cycle (using Bellman-Ford)
   b. Push flow around cycle (minimum residual capacity)
   c. Cost decreases by cycle_cost × flow_pushed
4. Return min-cost max-flow

Key insight: Negative cycles in residual graph indicate we can reduce cost by rerouting flow.

Complexity: O(V × E² × C × U) where C = max absolute cost and U = max capacity

• May need many cycle cancellations

Best for: Understanding the concept, small networks

2. Network Simplex

Strategy: Specialized linear programming for networks

How it works:

• Maintains a spanning tree structure (basis)
• Uses network structure for efficiency
• Pivots between spanning trees
• Much faster than general simplex

Complexity: Often polynomial in practice, exponential worst case

• Usually faster than cycle canceling

Best for: Large networks, production use

Comparison with Max-Flow

Aspect	Max-Flow	Min-Cost Max-Flow
Goal	Maximize flow	Maximize flow + minimize cost
Edge info	Capacity only	Capacity + cost
Complexity	O(VE²)	O(VE² × U) or higher
Applications	Simple routing	Cost optimization

Applications

Transportation & Logistics

• Package delivery: Deliver maximum packages at minimum cost
• Shipping: Route goods through cheapest paths
• Vehicle routing: Optimize delivery routes

Supply Chain

• Production planning: Optimize production and distribution
• Inventory management: Minimize storage and transport costs
• Resource allocation: Assign resources efficiently

Telecommunications

• Network routing: Route data through cheapest paths
• Bandwidth allocation: Maximize throughput, minimize cost
• Service provisioning: Optimize service delivery

Economics & Finance

• Market clearing: Clear markets with transaction costs
• Portfolio optimization: Maximize returns, minimize costs
• Resource trading: Optimize resource exchanges

Energy Systems

• Power distribution: Minimize transmission costs
• Gas pipelines: Optimize gas flow and costs

Example Scenario: Logistics Network

Network:
  Source → Warehouse A (capacity: 10, cost: 2/unit)
  Source → Warehouse B (capacity: 8, cost: 3/unit)
  Warehouse A → Warehouse B (capacity: 5, cost: 1/unit)
  Warehouse A → Sink (capacity: 12, cost: 1/unit)
  Warehouse B → Sink (capacity: 10, cost: 2/unit)

Problem: Maximize flow while minimizing total shipping cost.

Solution: Find optimal flow distribution:

• Use cheaper paths when possible
• Balance flow to minimize total cost
• Still achieve maximum flow

Complexity Analysis

Algorithm	Time Complexity	Notes
Cycle Canceling	O(VE² × U)	U = max capacity, many cycles
Network Simplex	Exponential worst, polynomial average	Fast in practice
Successive Shortest Path	O(V × E × max_flow)	Alternative approach

When to Use

✅ Use min-cost max-flow when:

• Both flow and cost matter
• Need optimal cost solution
• Network has cost information

❌ Use simple max-flow when:

• Only flow matters (cost irrelevant)
• Simpler problem
• Faster solution needed

Usage

# Run min-cost max-flow demo
./mincost_flow_example
 
# Compare algorithms
./mincost_flow_example --compare
 
# Test on specific network
./mincost_flow_example --network logistics
./mincost_flow_example --network assignment
./mincost_flow_example --network transportation
./mincost_flow_example --network all
 
# Show help
./mincost_flow_example --help

Note

In Aleph-w, max_flow_min_cost_by_cycle_canceling() returns (cycles_cancelled, it_factor); the maximum flow and the resulting minimum cost are read from the modified network (e.g. net.get_out_flow(net.get_source()) and net.flow_cost()).

See also

tpl_netcost.H Network with cost structures

tpl_mincost.H Minimum cost flow algorithms

network_flow_example.C Basic max-flow (no cost)

maxflow_advanced_example.cc Advanced max-flow algorithms

Author

Leandro Rabindranath León

Definition in file mincost_flow_example.cc.

Typedef Documentation

Arc

using Arc = CostNet::Arc

Definition at line 249 of file mincost_flow_example.cc.

CostNet

using CostNet = Net_Cost_Graph<Net_Cost_Node<string>, Net_Cost_Arc<Empty_Class, Flow_Type> >

Definition at line 247 of file mincost_flow_example.cc.

Flow_Type

using Flow_Type = double

Definition at line 246 of file mincost_flow_example.cc.

Node

using Node = CostNet::Node

Definition at line 248 of file mincost_flow_example.cc.

Function Documentation

build_simple_network()

CostNet build_simple_network

(

)

Build a simple logistics network.

Definition at line 254 of file mincost_flow_example.cc.

References Aleph::Net_Cost_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

Referenced by demo_compare_algorithms_on_logistics(), and demo_mincost_maxflow().

demo_assignment_problem()

void demo_assignment_problem

(

)

Demonstrate the assignment problem.

Definition at line 341 of file mincost_flow_example.cc.

References Aleph::maps(), and w.

Referenced by main().

demo_compare_algorithms_on_logistics()

static void demo_compare_algorithms_on_logistics ( )

static

Definition at line 273 of file mincost_flow_example.cc.

References build_simple_network(), Aleph::Net_Cost_Graph< NodeT, ArcT >::flow_cost(), Aleph::Net_Graph< NodeT, ArcT >::get_out_flow(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), Aleph::maps(), Aleph::max_flow_min_cost_by_cycle_canceling(), and Aleph::max_flow_min_cost_by_network_simplex().

Referenced by main().

demo_mincost_maxflow()

void demo_mincost_maxflow

(

)

Demonstrate min-cost max-flow.

Definition at line 421 of file mincost_flow_example.cc.

References build_simple_network(), Aleph::Net_Cost_Graph< NodeT, ArcT >::flow_cost(), Aleph::Net_Graph< NodeT, ArcT >::get_out_flow(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), Aleph::maps(), Aleph::max_flow_min_cost_by_cycle_canceling(), and print_cost_network().

Referenced by main().

demo_transportation_problem()

void demo_transportation_problem

(

)

Demonstrate the transportation problem.

Definition at line 383 of file mincost_flow_example.cc.

References Aleph::maps().

Referenced by main().

get_opt_value()

static const char * get_opt_value ( int  argc, char *  argv[], const char *  opt  )

static

Definition at line 237 of file mincost_flow_example.cc.

References Aleph::maps().

Referenced by main().

has_flag()

static bool has_flag ( int  argc, char *  argv[], const char *  flag  )

static

Definition at line 229 of file mincost_flow_example.cc.

References Aleph::maps().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 446 of file mincost_flow_example.cc.

References demo_assignment_problem(), demo_compare_algorithms_on_logistics(), demo_mincost_maxflow(), demo_transportation_problem(), get_opt_value(), has_flag(), Aleph::maps(), and usage().

print_cost_network()

void print_cost_network	(	CostNet &	net,
		const string &	title
	)

Print network with flows and costs.

Definition at line 305 of file mincost_flow_example.cc.

References GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), and Aleph::maps().

Referenced by demo_mincost_maxflow().

usage()

static void usage ( const char *  prog )

static

Definition at line 223 of file mincost_flow_example.cc.

References Aleph::maps().

Referenced by main().