ylfink@water.UUCP (07/14/87)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
NUMERICAL ANALYSIS SEMINAR
JOINT WITH COMBINATORICS & OPTIMIZATION
- Friday, July 17, 1987
Dr. A.R. Conn of the Computer Science Department will
speak on ``A Projection Method for the Uncapacitated
Facility Location Problem''.
TIME: 3:30 PM
ROOM: MC 3005
ABSTRACT
Several algorithms already exist for solving the
uncapacitated facility location problem. The most
efficient are based upon the solution of the strong
linear programming relaxation. The dual of this
relaxation has a condensed form which consists of
minimizing a certain piecewise linear convex function.
This talk presents a new method for solving the
uncapacitated facility location problem based upon the
exact solution of the condensed dual via orthogonal
projections. The amount of work per iteration is of
the same order as that of a simplex iteration for a
linear program in m variables and constraints, where
m is the number of clients. For comparison, the
underlying linear programming dual has mn+m+n
variables and mn+n constraints, where n is the
number of potential locations for the facilities. The
method is flexible as it can handle side constraints.
In particular, when there is a duality gap, the linear
programming formulation can be strengthened by adding
cuts. Numerical results for some classical test
problems are included.