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

# ###### The latest version of this IPython notebook is available at [http://github.com/jckantor/ESTM60203](http://github.com/jckantor/ESTM60203)  for noncommercial use under terms of the [Creative Commons Attribution Noncommericial ShareAlike License (CC BY-NC-SA 4.0)](http://creativecommons.org/licenses/by-nc-sa/4.0/).

# J.C. Kantor (Kantor.1@nd.edu)

# # Assignment Problems

# This [IPython notebook](http://ipython.org/notebook.html) demonstrates models for various types of assignment problems using GLPK/MathProg.

# ### Initializations

# In[1]:


from IPython.core.display import HTML
HTML(open("styles/custom.css", "r").read())


# ## Example Problem

# You work as a logistics manager for a toy manufacturer, and you currently have five delivery trucks on the road. Your trucks are in Austin, Boston, Chicago, Denver, Edmonton, and Fargo. You need them to drive to five other cities: Atlanta, Boise, Charlotte, Dallas, and Fresno. The table below shows the distance in miles between these cities.
# 
# | From\To  | Atlanta | Boise    | Charlotte | Dallas | Fresno |
# | : -----: | :-----: | :------: | :-------: | :----: | :----: |
# | Austin   | 921     | 1627     | 1166      | 196    | 1594   |
# | Boston   | 1078    | 2661     | 837       | 1767   | 3107   |
# | Chicago  | 716     | 1693     | 756       | 925    | 2140   |
# | Denver   | 1400    | 815      | 1561      | 788    | 1142   |
# | Edmonton | 3764    | 1718     | 3848      | 3310   | 2835   |
# 
# Where should you send each of your trucks in order to minimize travel distance?

# ### Combinatorial Complexity

# How many ways are there to assign destinations to each truck?
# 
# $N = 5 \times 4 \times 3 \times 2 \times 1 = 120$
# 
# In general there are 
# 
# $N = n!$ 
# 
# ways to assign $n$ resources to $n$ tasks.

# In[26]:


n = arange(0,10)
plot(n,n);
xlabel('Number of Resources/Tasks');


# In[28]:


xlabel('Number of Resources/Tasks')
plot(n,n,n,n**2)
legend(['n','n**2'],loc='best');


# In[29]:


xlabel('Number of Resources/Tasks')
plot(n,n,n,n**2,n,exp(n))
legend(['n','n**2','exp(n)'],loc='best');


# In[31]:


xlabel('Number of Resources/Tasks')
semilogy(n,n,n,n**2,n,exp(n),n,map(math.factorial,n))
legend(['n','n**2','exp(n)','n!'],loc='best');


# ### Types of Complexity
# 
# $$ Combinatoric >> Exponential >> Geometric >> Linear $$
# 
# Assignment problems can be incredibly difficult to solve. The speed of solution will depend on the exact details of the problem, what features can be left out without affecting the utility of the solution, and the availability of specialized algorithms.

# ## Formulation

# Let _x[R,T]_ be a binary variable where _x[R,T] = 1_ means resource _R_ is assigned to task _T_. 

# One resource must be assigned to each task. So for all $t\in TASKS$
# 
# $$\sum_{r \in RESOURCES} x[R,T] = 1$$  

# Each resource must be assigned to one task. So for all $r\in RESOURCES$
# 
# $$\sum_{t \in TASKS} x[R,T] = 1$$  

# In[9]:


get_ipython().run_cell_magic('writefile', 'Assign.mod', '\nset RESOURCES;\nset TASKS;\n\nparam a {RESOURCES,TASKS} >= 0;\n\nvar x {RESOURCES,TASKS} binary;\n\nminimize Cost: sum{r in RESOURCES, t in TASKS} a[r,t]*x[r,t];\nsubject to R {r in RESOURCES}: sum {t in TASKS} x[r,t] = 1;\nsubject to T {t in TASKS}: sum {r in RESOURCES} x[r,t] = 1;\n\nsolve;\n\nprintf "\\n\\n";\nfor {r in RESOURCES} {\n   for {t in TASKS : x[r,t] == 1} {\n      printf "Assign %10s   to %10s   Cost: %6.0f\\n", r, t, a[r,t];\n   }\n}\nprintf "\\n\\n";\n\nend;\n')


# ## Solution

# In[10]:


get_ipython().run_cell_magic('script', 'glpsol -m Assign.mod -d /dev/stdin', '\nset RESOURCES := Austin Boston Chicago Denver Edmonton ;\nset TASKS := Atlanta Boise Charlotte Dallas Fresno ;\n    \nparam a :   Atlanta\t Boise Charlotte Dallas Fresno :=\nAustin       921     1627    1166      196   1594\nBoston      1078     2661     837     1767   3107\nChicago      716     1693     756      925   2140\nDenver      1400      815    1561      788   1142\nEdmonton    3764     1718    3848     3310   2835 ;\n\nend;\n')


# ## Example

# A foreman has five workers and five jobs to complete. The
# time in hours each worker needs to complete each job is shown in the following
# table.
# 
# | Resource\Task | Job 1 | Job 2 | Job 3 | Job 4 | Job 5 |
# | :-----------: | :---: | :---: | :---: | :---: | :---: |
# | Worker 1      | 3     | 4     | 8     | 7     | 8     |
# | Worker 2      | 2     | 5     | 3     | 2     | 6     |
# | Worker 3      | 7     | 9     | 1     | 8     | 3     |
# | Worker 4      | 5     | 3     | 4     | 6     | 6     |
# | Worker 5      | 8     | 9     | 7     | 5     | 8     |

# ### What is the minimum time solution if one worker is assigned to each job?

# In[22]:


get_ipython().run_cell_magic('script', 'glpsol -m Assign.mod -d /dev/stdin', '\nset RESOURCES := Worker_1 Worker_2 Worker_3 Worker_4 Worker_5 ;\nset TASKS := Job_1 Job_2 Job_3 Job_4 Job_5 ;\n    \nparam a : Job_1\tJob_2 Job_3\tJob_4 Job_5 :=\nWorker_1\t3\t4\t8\t7\t8\nWorker_2\t2\t5\t3\t2\t6\nWorker_3\t7\t9\t1\t8\t3\nWorker_4\t5\t3\t4\t6\t6\nWorker_5\t8\t9\t7\t5\t8 ;\n\nend;\n')


# ### What is the minimum time solution if workers can be assigned multiple times?

# In[23]:


get_ipython().run_cell_magic('script', 'glpsol -m /dev/stdin', '\nset RESOURCES;\nset TASKS;\n\nparam a {RESOURCES,TASKS} >= 0;\n\nvar x {RESOURCES,TASKS} binary;\n\nmaximize Cost: sum{r in RESOURCES, t in TASKS} a[r,t]*x[r,t];\n#subject to R {r in RESOURCES}: sum {t in TASKS} x[r,t] = 1;\nsubject to T {t in TASKS}: sum {r in RESOURCES} x[r,t] = 1;\n\nsolve;\n\nprintf "\\n\\n";\nfor {r in RESOURCES} {\n   for {t in TASKS : x[r,t] == 1} {\n      printf "Assign %10s   to %10s   Cost: %6.0f\\n", r, t, a[r,t];\n   }\n}\nprintf "\\n\\n";\n\ndata;\n\nset RESOURCES := Worker_1 Worker_2 Worker_3 Worker_4 Worker_5 ;\nset TASKS := Job_1 Job_2 Job_3 Job_4 Job_5 ;\n    \nparam a : Job_1\tJob_2 Job_3\tJob_4 Job_5 :=\nWorker_1\t3\t4\t8\t7\t8\nWorker_2\t2\t5\t3\t2\t6\nWorker_3\t7\t9\t1\t8\t3\nWorker_4\t5\t3\t4\t6\t6\nWorker_5\t8\t9\t7\t5\t8 ;\n\nend;\n')


# ### Exercise
# 
# Suppose we want to assign just two workers. What is the minimum time solution using just two workers?

# ## Knapsack Problems

# ### Typical Applications
# 
# * Resource allocations with financial constraints
# * Construction and scoring of a heterogenous test
# * Selection of Capital Investments

# ### Example
# 
# Need to complete a set of jobs
# 
# 
# |       | A | B | C | D  | E  | F | G |
# |:-----:|:-:|:-:|:-:|:--:|:--:|:-:|:-:|
# | Value | 7 | 9 | 5 | 12 | 14 | 6 | 12 |
# | Time  | 3 | 4 | 2 | 6  | 7  | 3 | 5 |
# 
# 

# In[24]:


get_ipython().run_cell_magic('script', 'glpsol -m /dev/stdin', '\nset ITEMS;\n\nparam value{ITEMS};\nparam cost{ITEMS};\n\nvar x {ITEMS} binary;\n\nmaximize Obj: sum{i in ITEMS} value[i]*x[i];\nsubject to C: sum{i in ITEMS} cost[i]*x[i] <= 12 ;\n\nsolve;\n\nfor {i in ITEMS}{\n    printf "%3s  %2d\\n",i,x[i];\n}\n\ndata;\n\nparam : ITEMS : value cost :=\n A   7 3\n B   9 4\n C   5 2\n D  12 6\n E  14 7\n F   6 3\n G  12 5 ;\n            \nend;\n')


# ### Exercise
# 
# | Investment | Location | Cost (millions) | Expected Profit |
# | :--------: | :------: | :-------------: | :-------------: |
# | 1 | Europe   | 10 | 1.0 |
# | 2 | Europe | 8 | 0.9 |
# | 3 | Europe | 8 | 0.9 |
# | 4 | South America | 16 | 2.0 |
# | 5 | South America | 12 | 1.4 |
# | 6 | Africa | 4 | 0.2 |
# | 7 | Africa | 6 | 0.5 |
# | 8 | Africa | 16 | 2.1 |
# 
# The objective is to maximize the total expected profits subject to:
# 
# * Contractual commitments require at least 2 investments in Europe
# * There must be one South American Investment
# * No more than one African investment
# * Total cost must be less than $40 million
# 
# 
# 
# 

# In[ ]: