On Solving the Continuous Relaxation of a Linear Reformulation of the Two-Staged Assignment Problem

A class of mathematical programming problems which has received a great deal of attention over the past thirty years is that of facility location. Facility location problems, which deal with the strategic placement of facilities, are of interest to many groups of people due to their wide range of applications. They are, for example, of interest to the industrial engineer seeking to obtain more efficient ways to design and layout work space, to the urban planner desiring to effectively layout a city, and to the transportation scientist wishing to optimally direct flow throughout a network. While seemingly different, all of these problems seek to, in some fashion, strategically locate a number of (potential) facilities in such a manner that a cost is minimized, or a profit maximized. Costs can be measured in terms of monetary units, or may deal in other quantities such as time expended or distance traveled. The actual facilities vary in nature and may represent machines in a job shop to the industrial engineer, emergency medical facilities to the urban planner, or bus depots to the transportation scientist