#!/usr/bin/env python
# coding: utf-8

# # The $p$-Median Problem
# 
# ## Summary
# 
# The goal of the $p$-median problem is to locating $p$ facilities to minimize the demand weighted average distance between demand nodes and the nearest of the selected facilities. Hakimi (1964, 1965) first considered this problem for the design of network switch centers. 
# However, this problem has been used to model a wide range of applications, such as warehouse location, depot location, school districting and sensor placement.
# 
# 
# ## Problem Statement
# 
# The $p$-median problem can be formulated mathematically as an integer programming problem using the following model.  
# 
# ### Sets
# 
#  $M$ = set of candidate locations  
#  $N$ = set of customer demand nodes
# 
# ### Parameters
# 
#  $p$ = number of facilities to locate  
#  $d_j$ = demand of customer $j$, $\forall j \in N$  
#  $c_{ij}$ = unit cost of satisfying customer $j$ from facility $i$, $\forall i \in M, \forall j \in N$
#  
# ### Variables
#  $x_{ij}$ = fraction of the demand of customer $j$ that is supplied by facility $i$, $\forall i \in M, \forall j \in N$  
#  $y_i$ = a binary value that is $1$ is a facility is located at location $i$, $\forall i \in M$
# 
# ### Objective
# 
# Minimize the demand-weighted total cost  
#  $\min \sum_{i \in M} \sum_{j \in N} d_j c_{ij} x_{ij}$
# 
# ### Constraints
# 
# All of the demand for customer $j$ must be satisfied  
#  $\sum_{i \in M} x_{ij} = 1$, $\forall j \in N$
# 
# Exactly $p$ facilities are located  
#  $\sum_{i \in M} y_i = p$
#  
# Demand nodes can only be assigned to open facilities  
#  $x_{ij} \leq y_i$, $\forall i \in M, \forall j \in N$
#  
# The assignment variables must be non-negative  
#  $x_{ij} \geq 0$, $\forall i \in M, \forall j \in N$
# 
# ## Pyomo Formulation
# 
# The following is an abstract Pyomo model for this problem:

# In[1]:


get_ipython().system('cat p-median.py')


# ****
# This model is simplified in several respects.  First, the candidate locations and customer locations are treated as numeric ranges.  Second, the demand values, $d_j$ are initialized with a default value of $1$.  Finally, the cost values, $c_{ij}$ are randomly assigned.
# 
# ## Model Data
# 
# This model is parameterized by three values: the number of facility locations, the number of customers, and the number of facilities.  For example:

# In[2]:


get_ipython().system('cat p-median.dat')


# ****
# 
# ## Solution
# 
# Pyomo includes a `pyomo` command that automates the construction and optimization of models.  The GLPK solver can be used in this simple example:

# In[3]:


get_ipython().system('pyomo solve --solver=glpk p-median.py p-median.dat')


# By default, the optimization results are stored in the file `results.yml`:

# In[4]:


get_ipython().system('cat results.yml')


# ****
# 
# This solution places facilities at locations 3, 6 and 9.  Facility 3 meets the demand of customer 4, facility 6 meets the demand of customers 1, 2, 3 and 5, and facility 9 meets the demand of customer 6.

# ## References
# 
# * S.L. Hakimi (1964) Optimum location of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459
# * S.L. Hakimi (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper Res 13:462–475