see the Integrated Logistics Workshop's website

Anant
Balakrishnan
McCombs School of Business,
The University
of Texas at
Austin

Network Design Models for Distribution Systems

Network design models, incorporating tradeoffs between fixed investments in links or services and operational or variable costs of routing flows, arise in a variety of strategic, tactical, and operational planning contexts in distribution management, ranging from supply chain configuration to detailed routing and scheduling. This talk will provide an overview of network design models, their applications, and solution methods. We present a modeling framework, encompassing variants and extensions of the network design model, discuss representative applications in logistics, and outline solution approaches that have proven effective.

Preliminary presentation: (pdf)

Building Edge-Failure Resilient Networks

We consider the design of resilient networks that are fault tolerant against link failures. Resilience against link failures can be built into the network by providing backup paths, which are used when an edge failure occurs on a primary path. We consider several network design problems in this context: the goal is to provision primary and backup bandwidth while minimizing cost. Our models are motivated by current high speed optical networks and we provide approximation algorithms for the problems.

Joint work with Anupam Gupta, Amit Kumar, Seffi Naor, and Danny Raz.

Preliminary presentation: (pdf) (ppt)

Simultaneous Optimization with Concave Costs or Concave Profits

In simultaneous optimization, we need to simultaneously approximate a whole family of objective functions. In this talk, we will consider two problems:

a) Suppose we want to construct a tree for sending information from a single source to k sinks. Further, suppose that  the cost of sending x units of information over a link is proportional to f(x), where f is concave, f(0) = 0, and f is non-decreasing. This problem is known as single source buy-at-bulk network design. We will present a simple randomized algorithm that guarantees an O(log k) approximation to the cheapest tree for all such functions f, simultaneously.

b) Suppose we want to assign bandwidth to N network connections, and the utility of the system is some symmetric concave function, U, of assigned bandwidths. We present a simple distributed algorithm, based on the primal-dual approach, that simultaneously provides a logarithmic approximation for all U.

Part (a) represents joint work with Deborah Estrin and (b) represents joint work with Sung-woo Cho.

Marc
Goetschalckx
Georgia Institute of Technology

Modeling of Strategic Supply Chain Design Problems Under Uncertainty

Preliminary presentation: (pdf)

Approximation Algorithms for Data Placement on Parallel Disks

We study a problem that arises in the context of data placement in multimedia storage systems. We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks. We are also given the demand for each data item. Each data item has a size s_i. Disks are typically characterized by two parameters, its storage capacity k, and a load capacity L which indicates the maximum number of users that it can serve. The goal is to find a placement of data items on the disks and an assignment of users to disks so as to maximize the total number of users served, subject to the capacity constraints of the storage system.

The talk presents the first successful attempt at removing the assumption that all data items have unit size. We develop a polynomial time approximation scheme (PTAS) for all instances where s_i in {1,...,D} for some constant D.

The talk also presents an algorithm for which we can prove tight bounds on the number of users that can be served, regardless of the input distribution, when s_i in {1,2}. In other words there are instances where no placement of data items and assignment of load can guarantee a better packing.

This is a joint work with Samir Khuller.

Preliminary presentation: (pdf)

Algorithms for Data Migration with Cloning

Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers, or multimedia servers for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. In this work we study the  data migration problem, which arises when we need to quickly change one storage configuration into another. We show that this problem is NP-hard. In addition, we develop polynomial time approximation algorithms for this problem and prove a worst case bound of 9.5 on the approximation factor achieved by our algorithm. We also compare the algorithm to several heuristics for this problem.

Joint work with Yoo Ah Kim and Justin Wan.

A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem

In this talk, I shall present the first constant-factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity buy-at-bulk network design in which there are two ways to install capacity on any given edge.  Capacity can be rented, with cost incurred on a per-unit of capacity basis, or  bought, which allows unlimited use after payment of a large fixed cost.  Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink.

Recent work on buy-at-bulk network design has concentrated on the special case where all sinks are identical; existing constant-factor approximation algorithms for this special case make crucial use of the assumption that all commodities ship flow to the same sink vertex and do not obviously extend to the multicommodity rent-or-buy problem.  Prior to our work, the best heuristics for the multicommodity rent-or-buy problem achieved only logarithmic performance guarantees and relied on the machinery of relaxed metrical task systems or metric embeddings. By contrast, we solve the network design problem directly via a novel primal-dual algorithm.

This is joint work with Anupam Gupta and Tim Roughgarden.

Preliminary presentation: (pdf) (ppt)

Designing Overlay Multicast Networks for Streaming

Locating Nursing Stations: Covering Graphs Using Trees and Stars

A tree cover of a graph $G$ is defined as a collection of trees such that their union includes all the vertices of $G$. The weight of a tree cover is the weight of the maximum weight tree in the tree cover. Given a positive integer $k$, the $k$-tree cover problem is to compute a minimum cost tree cover which has no more than $k$ trees. Star covers are defined analogously. Additionally, we may also be provided with a set of $k$ vertices which are to serve as roots of the trees or stars. In this paper, we provide constant factor approximation algorithms for finding tree and star covers of graphs, in the rooted and unrooted versions.

Joint work with Guy Even, Naveen Garg, Jochen Konemann and R. Ravi.

Preliminary presentation: (pdf)

Nash Equilibria in a New Connection Game

We introduce a new game in which players seek to connect pairs of terminals in a graph. Players are allowed to share edges that are fully paid for, and each player seeks to pay as little as possible while still connecting his terminals. The centralized version of this game is simply the generalized Steiner tree problem. However, in a game where all agents act selfishly, there may be no stable solution, i.e. a Nash equilibrium may not exist. We explore some situations where equilibria do exist, and develop bi-criteria approximations for studying solutions which are nearly stable.

This is part of joint work with Elliot Anshelevich, Anirban Dasgupta, and Eva Tardos to appear in STOC 03.

Preliminary presentation: (pdf) (ppt)

Logistics and communication networks designed from a pure cost-efficiency perspective tend to be sparse and have little spare capacity. Consequently, edge failures in such networks can lead to the disruption of service between many pairs of network locations, possibly resulting in severe economic losses. In this paper, we consider the problem of designing cost-effective, but failure-tolerant networks. Given a network with required connectivity levels, specified as the number of edge-disjoint paths needed between each node pair, we seek the minimum cost topological design that meets these connectivity requirements. Even the simplest special cases of this problem are computationally difficult. We propose a new flow-based approach for modeling this problem, and develop valid inequalities that further strengthen this formulation. Our preliminary computational results for problem instances having up to 400 integer variables show that our procedure generates solutions that are on average within 1 % of optimality in a reasonable amount of computational time.

This work is joint with Anant Balakrishnan.

Preliminary presentation: (pdf)

In this talk we will consider several network design games with selfish agents.

Maybe the simplest network design games are facility location and spanning tree-games when goal of each player is to connect a terminal to a facility or to a common source in the graph. Facilities, and potential edges in the network have costs and each agent's goal is to pay as little as possible, while having his terminals connected. We will consider these and related games both from the perspective of cost sharing, and that of the quality of Nash equalibria.

The result presented are joint work with Elliot Anshelevich, Anirban Dasgupta, Martin Pal, and Tom Wexler.

Multicommodity Rent or Buy: Approximation via Cost-Sharing

In the Steiner forest problem we are given a graph and a set of pairs of demands that need to communicate. The goal is to buy a set of edges so that each pair is connected by a path. In the multicommodity rent or buy problem we can for each edge choose either to buy it at a high fixed cost, or rent it, paying rental cost for each path using the edge.

In this talk I will present a cost sharing algorithm for the Steiner forest problem and show how this algorithm together with a simple randomized analysis yields a constant factor approximation algorithm fo the multicommodity rent or buy problem. The cost shares are generated by a natural dual growing process, while the Steiner forest is constructed by a procedure that can be viewed as an "inflated version" of the Steiner forest algorithm by Agarwal, Klein and Ravi, and Goemans and Williamson.

Joint work with Anupam Gupta, Amit Kumar, and Tim Roughgarden.

Preliminary presentation: (ppt) (pdf)

The Optimal Design and Operation of Remnant Inventory Systems

This presentation discusses the integrated design and operation of an inventory control and distribution system for remnant inventory.  Such inventory is encountered in the supply chains of various one-dimensional products such as rolls of steel, aluminum, paper, fabric, etc. where the product is produced in "standard" sizes but demands occur in "nonstandard" sizes.   This ongoing research (a) combines elements of several classical O.R. problem areas including the cutting stock problem, inventory management, facility location, and distribution, and (b) proposes the use of several different O.R. techniques such as Benders’ decomposition, stochastic programming, and remnant inventory control. Based on earlier work by Adelman and Nemhauser, a combined location/distribution network model is described for the problem where locations for both inventory distribution points and demand are geographically dispersed.  We also assume that scrap can be recycled, and discuss extensions such as stochastic demand and raw material sizing.