Lecture 1. Overview of mathematical models and algorithms for solving the p-median problem.
Lecture 2. Pseudo-Boolean approach to the p-median problem based on general purpose solvers.
Lecture 3. Algebra of equivalent instances and its applications.
Lecture 4. Theory and computational experiments with benchmarks p-median instances.
The objective of the p-Median problem (PMP) is to locate p facilities (medians) such that the sum of the distances from each demand point to its nearest facility is minimized. A justiification for this research is that there is an evidence (see e.g. Brusco and Kohn 2008) that the PMP can provide better cluster reconstruction than alternative clustering procedures (the complete and average linkage, minimum variance, and K-means).
In the first lecture we overview the state-of-the-art for PMP models and algorithms and show that PMP instances with the number of potential sites more than 600 even cannot be downloaded by means of general purpose software like CPLEX.
Our second lecture is devoted to design an almost optimal mathematical programming model for the PMP within the class of Mixed Integer Linear Programming (LP) Models with the following details. We formulate the PMP as a minimization problem of a pseudo-Boolean polynomial (pBp) and linearize all non-linear terms in pBp by means of new variables and linear constraints reflecting the relationships between all embedded terms in pBp. The number of new variables is equal to the number of linear constraints and both of them decrease with increasing the number p of medians. Moreover, both of these numbers are minimal within the class of mixed Boolean LP models. We discuss different pre-processing algorithms and indicate some new directions for research based on the data correcting approach.
The third lecture presents instances of this problem that are equivalent, in the sense that each feasible solution has the same objective 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 and describe some natural properties of the corresponding polyhedra in terms of classical linear algebra. Based on the properties of PMP described in the second lecture we justify a new class of PMP benchmark instances and show by means of computational experiments that there relatively small PMP instances with just a few hundreds of sites and p = 5; 10 which are computationally difficult for general purpose solvers.
In the final lecture we consider two important applications of the PMP to cell formation in group technology and margin calculations in the brokerage industry. We give an introductory description to both applications and emphasize that this mini-course is intended for everybody who is interested in operations research, combinatorial optimization and their applications to industrial problems.
Language of the course — English.
Tutors of the course:
Prof. B. Goldengorin, University of Groningen, The Netherlands
D. Krushinsky, University of Groningen, The Netherlands