A Projection Method for the Uncapacitated Facility Location Problem.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA181661

Entities

People

  • A. R. Conn
  • G. Cornuejols

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Cost Models
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Perturbations
  • Schools
  • Simplex Method
  • Stationary
  • Test Sets
  • Universities

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Combustion Dynamics and Shock Wave Physics.
  • Graph Algorithms and Convex Optimization.