
Accession Number : ADA181661
Title : A Projection Method for the Uncapacitated Facility Location Problem.
Descriptive Note : Management Sciences Research rept.,
Corporate Author : CARNEGIEMELLON 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