A Canonical Representation of Simple Plant Location Problems and Its Applications
Authors:
- Gerard CornuejolsGCGerard Cornuejols
- George L. NemhauserGNGeorge L. Nemhauser
- Laurence A. WolseyLWLaurence A. Wolsey
- 1 September 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 1 (3) , 261-272
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.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Worst-Case and Probabilistic Analysis of Algorithms for a Location ProblemOperations Research, 1980
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Best Algorithms for Approximating the Maximum of a Submodular Set FunctionMathematics of Operations Research, 1978
- An analysis of approximations for maximizing submodular set functions—II1978
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977
- Algorithms for Exploiting the Structure of the Simple Plant Location Problem1977
- Implicit representation of variable upper bounds in linear programming1975