Transcript Network Design Problems

Algorithms for Concave
Cost Network Flow Problems
Kamesh Munagala
Stanford University
Talk Outline

Motivation via simple example

Concave cost flow problem:



Formal problem statement
Simple Randomized Algorithm
Special Cases:



Motivation from networking problems
Our results
The buy-at-bulk algorithm
Cost Structures in Network Design
Warehouse Location
Decision Problem

Costs:



Opening and operating warehouse
Shipping demand
Tradeoff: Lots of warehouses implies low shipping cost

Optimize: Linear combination of costs

Decisions:



How many warehouses to open
Where to open warehouses
How to ship to outlets
Warehouse Cost


Minimum fixed cost for
operating warehouse
Additional cost depending
on storage capacity
needed


Typically reduces as
capacity increases
Example: Staff does not
double with doubling
capacity
Cost
Fixed
Cost
Storage Capacity
Transportation Cost


Linear in distance to
outlet
Cost
Linear in load
transported to outlet

Minimum fixed cost
for one truck
One
Truck
Load Transported
Features of Cost Structure

Economies of Scale



Discreteness in quantity



More capacity cheaper per unit demand
Applies to warehouse costs
Cannot purchase arbitrarily small capacity
Applies to warehouse and transportation costs
General phenomena in network design:

Costs of caches, routers and cables obey these properties
Modeling Allocation Costs

Cost is:


Cost
non-decreasing
concave
function of demand
serviced
0
Demand
Concave Cost Flow Problem
Concave Cost Flow Problem
 Given:
Sink
 Undirected network

Cost on edges



Concave function of demand
Many demand nodes
Distinguished sink node
Sources

Compute:

Minimum cost flow
Facility Location
Warehouse cost = f(i)
Warehouse i
Transportation
Cost = c(i,j)
Outlet j
Demand d(j)
Optimize:  c(i,j) d(j) +  f(i)
Modeling Facility Location
Sink
f(i)
i
c(i,j)
d(j)
Optimize:  c(i,j) d(j) +  f(i)
Solution
Sink
Other Special Cases

Steiner Trees
Probabilistic Steiner Trees [KM00]
Multilevel Facility Location
Buy at Bulk Network Design [SCRS97]

Applications in network design:







Multicast tree design
Hierarchical placement of caches and routers
Placement of web content in caches
Buying cables to provision bandwidth

Facility location is NP-Hard
Cost
Hardness of the Flow Problem
1

Steiner Tree Problem:


Fixed cost for using edge
NP-Hard [Karp. 1972]
0
Flow
Sink

Approximation algorithms:

Provably close to optimal
solution on all instances


Example: Cost  5 OPT
Polynomial running time
1
3
2
Flow = 1
Cost = 5
1
Previous Results
 Operations Research:
 Uncapacitated Fixed Charge Problem
 Magnanti, Mireault, Wong. 1986
 Hochbaum, Segev. 1989
 Ortega, Wolsey. 2000

No approximation algorithms known for this problem
Our Result

Logarithmic approximation


Properties of our algorithm:

Simple to implement




[Meyerson, Munagala, Plotkin. 2000]
Uses shortest path and greedy matching computations
Efficient in practice
Approximation ratio much better on real data
Subsequent Results:



Best approximation result till date
De-randomization
[Chekuri, Khanna, Naor. 2001]
Best hardness: 1.47
[Guha, Khuller. 1998]
Basic Algorithm

Merging demand reduces cost:







For every pair (u,v) compute min cost
path in graph to send demand from u
to v or vice versa
Let this be cost of (u,v) edge
Compute min cost matching in this
complete graph
Pair demands using this matching
Choose one node in pair as center and
send demand to it
Number of demand nodes halves
Repeat logarithmic times
Proof Idea



The optimal solution encodes a matching of nodes
Implies cost of matching at most cost of optimal solution
[Marathe et al 1998]
s
Matching in OPT’s solution
u
v
Problem too hard?

Which node is cheaper to route to depends
on demand being routed


Hard to make decisions about merging a whole
group of nodes
Not enough structure in solution


Except for the fact that it encodes a matching
Best hardness result known is only 1.47

Guha, Khuller. 1998
Special Cases of
Concave Cost Flow
Facility Location
Warehouse cost = f(i)
Warehouse i
Transportation
Cost = c(i,j)
Outlet j
Demand d(j)
Optimize:  c(i,j) d(j) +  f(i)
Previous Results

Operations Research:



Approximation Algorithms:




Kuehn, Hamburger. 1963
Cornuejols, Fisher, Nemhauser. 1977
Guha, Khuller. 1998
(Lower bound = 1.47)
Mahdian, Ye, Zhang. 2002 (1.52 approx)
Fast combinatorial algorithms known [CG99,JV99,AGKMMP01]
Applications:


Centroid based clustering
Placement of caches and replicated data objects:
 Minimize latency of user access
Our Result

Novel variant of facility location:



Each facility needs to satisfy minimum amount of demand
Load Balanced facility location
Constant factor approximation algorithm [KM00,GMM00]


Reduction to classical facility location
Applications:


Subroutine in concave cost flow algorithms
Solving clustering variants [GM02]

Favor either large or small cluster sizes
Multilevel Facility Location
Production Units
g(k)
c(k,i)
Warehouses
f(i)
c(i,j)
Outlets
d(j)
2-level Warehouse Location
Previous Results

Problem formulation:


Kaufman, vanden Eede. Hansen, 1977
Factor 3 approximation:


Aardal, Chudak, Shmoys. 1999
Exponential size linear program



Can be solved using Ellipsoid algorithm
Very inefficient in practice
Application in networks:

Hierarchical placement of caches, switches and routers
Modeling as a Flow Problem
Two copies of the network
Outlets
f(i)
i
i
g(k)
k
c(i,j)
c(i,j)
Route flow from outlets to the sink node
Sink
Our Results
 Simple combinatorial algorithm:
 9 approximation [GMM00]
 Reduce to classical facility location
 Can now use very efficient algorithms
 Subsequent results:
 3.27 approximation
 Ageev, Ye, Zhang. 2002
 Combinatorial algorithm
Buy-at-bulk Network Design

Provisioning cables to route data to core network

Bandwidth cost obey economies of scale

Cable types:




T1:
T3:
1.5 Mbps $30/mile
44 Mbps $440/mile
$20/Mbps/mile
$10/Mbps/mile
Cost of cables is a concave function
Metrical special case:

Cost of bandwidth same per unit length everywhere
Concave function same per unit length on all edges

[Salman, Cheriyan, Ravi, Subramanian. 1997]

Why is this problem simpler?

Notion of close-by:

If dist(a,b) < dist(a,c)



Natural algorithm:



Cheaper to transport demand from a to b than to c
Independent of demand transported
Merge close-by demands together
Cheaper to transport this merged demand to a far away
place
General concave cost flow:

Closeness is a function of demand transported
Recursive Metric Partitioning

Just focus on the metric space


Ignore the cost function completely
Recursively partition graph based on closeness (randomized):

Partitions have smaller diameter than original graph





[Bartal96, Bartal98, CCGG98, CCGGP98]
Nodes in different partitions far away from each other w.h.p.
For each partition, have a center node
Collect all demand within a partition at center node
Send this demand to the center of the parent of this partition

[Awerbuch, Azar. 1997]
Partitioning
Diameter of Graph = D
Diameter < D/2
w.h.p. Distances > D/log n
Routing
Route from centers of children to center of parent
Discussion

Paradigm of aggregation:



Group together close-by demand nodes
Reduce cost of transportation
Problems with approach:

Same partition for all cost functions

Some close-by nodes bound to end up in different partitions


Problem even if graph is just a cycle
Worst case logarithmic performance expected in practice
Other Approaches

Linear Programming:




Andrews and Zhang. 1998
Improve the logarithmic ratio for special cases
Usually produces optimal integer solutions in practice
The size of the program is huge:



N3 variables
Inefficient in practice
Simple algorithms known for very special cases:

Salman, Cheriyan, Ravi, Subramanian. 1997
Our Solution Idea

Use cost function to construct the partitioning:



Say we have T1 and T3 lines
Say cheaper to use T3 line if bandwidth > 10Mbps
Then, we should find:





Min cost way of aggregating demands using T1 lines
Each aggregated node receives 10Mbps bandwidth
Min cost way of connecting aggregated nodes to sink node
Construct partitioning bottom-up instead of top-down
Properties of partition:


Close-by demands still grouped together
The cost function decides group boundaries
First Aggregation Step
Partition assuming T3 line becomes cheaper at 10 Mbps bandwidth
Aggregation point
Groups with 10 Mbps
total bandwidth
T1 lines
Complete Solution
T3 lines
Constructing the Partitions

Given:


A set of demand nodes
Length metric on edges
Demand > U

Select: Set of aggregation points




Load Balanced Facility Location


Send at least U demand per point
Route along shortest paths
Minimize total routing cost
O(1) approximation [KM00,GMM00]
Iteratively construct larger partitions
One Issue
Routing with a cable type need not be along shortest paths
Capacity = 1
1
Cost/Length = 1
1
0.5
Case 1: Cost = 1.5
Case 2: Cost = 2.5
Cost = 2
Cost = 2
Demand = 0.5
Demand = 1.0
Another Issue

We are constructing partition bottom-up




Scaling technique:




Optimal partition could look different
If we make error in first grouping, error propagates upward
How do we bound cost against optimal cost
Observation: Error propagates only if similar cable types exist
Eliminate all cable types that look similar except one
Partitioning at every stage close to optimal partitioning
Constant factor approximation [GMM00,GMM01]
Properties of Algorithm

Simple to implement:



Uses facility location and Steiner trees as subroutines
Very efficient in practice
Preliminary experimental results:




Real ISP and geographic data
Real cable types and costs
At most 10% away from optimal solution
Subsequent work:



Talwar. 2002
Gupta, Kumar, Roughgarden. 2003
Based on the ideas in our algorithm
(213 approx)
(72 approx)
Open Problems

Better approximation ratios:



Buy-at-bulk: 72 [GKR03]
Concave cost flow: Logarithmic approximation [MMP00]
Multiple sink concave cost flow:


Aggregation paradigm fails!
Buy-at-bulk problem:


Logarithmic approximation [AA97]
Aggregation paradigm applicable to other problems?
Acknowledgements
Research collaborators:

Serge Plotkin, Stanford University
Abhiram Ranade, IIT Bombay

Sudipto Guha and Adam Meyerson





Matthew Andrews, Bell Laboratories
Pat Brown, Stanford University School of Medicine
Ramesh Hariharan, Strand Genomics Pvt. Ltd.
Zoe Abrams, Ashish Goel, Baruch Schieber, Debasis Mitra, Devavrat
Shah, Jochen Konemann, Maxim Sviridenko, Rina Panigrahy, Rob
Tibshirani, Shankar Krishnan, Suresh Venkat and Tracy Kimbrel
Acknowledgements
Theory wing:

Mayur Datar, Aris Gionis, Gagan Aggarwal, Keyvan Mohajer, Liadan
O’Callaghan, Majid Emami, Moses Charikar and Piotr Indyk
Friends :
 Dhananjay Gore, Rohit Nabar, Aditi Nabar, Kumar Muthuraman, Mohan
Lakhamraju, Nandan Das, Prashanth Hande and Sameer Siruguri
Parents and Roopa