Accession Number : ADA181661

Title :   A Projection Method for the Uncapacitated Facility Location Problem.

Descriptive Note : Management Sciences Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Conn,A R ; Cornuejols,G

PDF Url : ADA181661

Report Date : Jan 1987

Pagination or Media Count : 36

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 paper 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.

Descriptors :   *FACILITIES, *LINEAR PROGRAMMING, *POSITION(LOCATION), ALGORITHMS, CONVEX BODIES, FUNCTIONS(MATHEMATICS), LINEARITY, RELAXATION, VARIABLES, FORMULATIONS, ORTHOGONALITY, PROJECTIVE TECHNIQUES, PROBLEM SOLVING, ITERATIONS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE