EQUIVALENT INSTANCES OF THE SIMPLE PLANT LOCATION PROBLEM: A PSEUDO-BOOLEAN APPROACH
Professor Boris Goldengorin, Department of Econometrics and Operations Research, University of Groningen, The Netherlands

Abstract: In this talk we deal with a pseudo-Boolean representation of the simple plant location problem. We define instances of this problem that are equivalent, in the sense that each feasible solution has the same goal function value in all such instances. We further define a collection of polytopes whose union describes the set of instances equivalent to a given instance. We use the concept of equivalence to develop a method by which we can extend the set of instances that we can solve using our knowledge of polynomially solvable special cases. We also present a new preprocessing rule that allows us to determine sites in which facilities will not be located in an optimal solution and thereby reduce the size of a problem instance.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 2 February 2001.

back