BOOLEAN AND GRAPH THEORETIC FORMULATIONS OF THE SIMPLE PLANT LOCATION PROBLEM

A formulation of the simple plant location problem as the minimization of a pseudo-Boolean function is transformed into a set covering problem and into a weighted vertex packing problem on a graph, called the "plant location graph. " For the special case of a simple plant location problem derived from a tree network, the plant location graph is shown to be weakly triangulated, so that a maximum weighted vertex packing can be found in polynomial-time by existing algorithms.