Approximating Optimal Control of Fluid Networks
Lisa Fleischer, Carnegie Mellon (GSIA)

Abstract:

We consider a broad class of separated continuous linear programs (SCLP) that arise as fluid relaxations of multiclass queueing networks, and are used to find approximate solutions to complex job shop scheduling problems. One example of a problem we consider is the multicommodity flow problem with holding costs: Given a capacitated network with node queues, linear flow costs and linear, per-unit-time holding costs, drain the queues to minimize total holding costs. The complexity of this problem is not well understood, but there is evidence to suggest that optimal solutions may have exponential size. Existing algorithms for SCLP
do not have polynomial time or space guarantees.

For given constants a > 0 and b > 0, we present an algorithm that finds a solution with value at most (1+a)OPT + b, where OPT is the value of the optimal solution. The complexity of our algorithm and the size of the solution we produce are polynomial in the size of the input network, 1/a, and log(1/b). We introduce a natural discretization of polynomial size and prove that this discretization produces a solution with low cost. This is the first polynomial time algorithm with a provable approximation guarantee for solving fluid relaxations.

This is joint work with Jay Sethuraman, Columbia University.