A Canonical Representation of Simple Plant Location Problems and Its Applications

Authors:
  • GCGerard Cornuejols
    Gerard Cornuejols
  • GNGeorge L. Nemhauser
    George L. Nemhauser
  • LWLaurence A. Wolsey
    Laurence A. Wolsey

Abstract
We consider a location problem whose mathematical formulation is $\max_S \{ v( S ): S \subseteq N,|S| = K \}$ where $v ( S ) = v ( \emptyset ) + \sum_{i \in I} \max_{j \in S} c_{ij}, C = ( c_{ij} )$ is a real matrix with row index set $I = \{ 1, \cdots ,m \}$ and column index set $N = \{ 1, \cdots ,n \}$ and $K\leqq n$ is a positive integer. A set function of the form $v ( S )$ is called a simple location function. We give a constructive proof that a set function w is a simple location function if and only if it can be represented in the canonical form $w ( S ) = r_\emptyset + \Sigma _{T \cap S \ne \emptyset } r_T $ with $r_T \geqq 0$ for all $\emptyset \subset T \subset N$. The proof is also a polynomial algorithm for reducing the matrix C to the canonical form. We give two applications of this canonical representation. The first is that a large class of algorithms for the location problem need to enumerate all but l of the feasible solutions in order to find one of the lth best solutions. The second application is the derivation of new integer programming formulations of the location problem. Some of these formulations seem to be easier to solve than the standard one. We conclude the paper with two alternate representations of set functions and, in each case, characterize the nondecreasing, submodular and simple location functions.