# Decentralization Planning

## Objective and Prerequisites

Ready for a mathematical optimization modeling challenge? Put your skills to the test with this example, where you’ll learn how to model and solve a decentralization planning problem. You’ll have to figure out – given a set of departments of a company, and potential cities where these departments can be located – the “best” location for each department in order to maximize gross margins.

This model is example 10 from the fifth edition of Model Building in Mathematical Programming by H. Paul Williams on pages 265 and 317-319.

This modeling example is at the advanced level, where we assume that you know Python and the Gurobi Python API and that you have advanced knowledge of building mathematical optimization models. Typically, the objective function and/or constraints of these examples are complex or require advanced features of the Gurobi Python API.

**Download the Repository** <br /> 
You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). 

## Problem Description

A large company wants to move some of its departments out of London. Doing so will result in reduced costs in some areas
(such as cheaper housing, government incentives, easier recruitment, etc.), and increased costs in other areas (such as communication between departments). The cost implications for all possible locations of each department have been calculated.
The goal is to determine where to locate each department in order to maximize the total difference between the reduced costs  from relocating and the increased communication costs between departments.

The company comprises five departments (A, B, C, D and E). The possible cities for relocation are Bristol and Brighton, or a department may be kept in London. None of these cities (including London) may be the location for more than three of the departments.

## Model Formulation

### Sets and Indices

$d,d2 \in \text{Departments}=\{A,B,C,D,E\}$

$c,c2 \in \text{Cities}=\{\text{Bristol}, \text{Brighton}, \text{London}\}$

### Parameters

$\text{benefit}_{d,c} \in \mathbb{R}^+$: Benefit -in thousands of dollars per year, derived from relocating department $d$  to city $c$.

$\text{communicationCost}_{d,c,d2,c2} \in \mathbb{R}^+$: Communication cost -in thousands of dollars per year, derived from relocating department $d$  to city $c$ and relocating department $d2$  to city $c2$.

We define the set $dcd2c2 = \{(d,c,d2,c2) \in \text{Departments} \times \text{Cities} \times \text{Departments} \times \text{Cities}: \text{communicationCost}_{d,c,d2,c2} > 0  \}$

### Decision Variables

$\text{locate}_{d,c} \in \{0,1 \}$: This binary variable is equal 1, if department $d$  is located at city $c$, and 0 otherwise.

$y_{d,c,d2,c2} = \text{locate}_{d,c}*\text{locate}_{d2,c2} \in \{0,1 \}$: This auxiliary binary variable is equal 1, if department $d$ is located at city $c$ and department $d2$ is located at city $c2$, and 0 otherwise. 


### Constraints

**Department location**: Each department must be located in only one city.

\begin{equation}
\sum_{c \in \text{Cities}} \text{locate}_{d,c} = 1 \quad \forall d \in \text{Departments}
\end{equation}

**Departments limit**: No city may be the location for more than three departments.

\begin{equation}
\sum_{d \in \text{Departments}} \text{locate}_{d,c} \leq 3 \quad \forall c \in \text{Cities}
\end{equation}

**Logical Constraints**: 

- If $y_{d,c,d2,c2} = 1$ then $\text{locate}_{d,c} = 1$ and $\text{locate}_{d2,c2} = 1$.

\begin{equation}
y_{d,c,d2,c2} \leq \text{locate}_{d,c} \quad \forall (d,c,d2,c2) \in dcd2c2
\end{equation}

\begin{equation}
y_{d,c,d2,c2} \leq \text{locate}_{d2,c2} \quad \forall (d,c,d2,c2) \in dcd2c2
\end{equation}

-  If $\text{locate}_{d,c} = 1$ and $\text{locate}_{d2,c2} = 1 $ then $y_{d,c,d2,c2} = 1$.


\begin{equation}
\text{locate}_{d,c} + \text{locate}_{d2,c2} - y_{d,c,d2,c2} \leq 1 \quad  \forall (d,c,d2,c2) \in dcd2c2
\end{equation}

### Objective Function

**Gross margin**: Maximize the gross margin of relocation.

\begin{equation}
\text{Maximize} \quad Z = \sum_{d \in \text{Departments}} \sum_{c \in \text{Cities}} \text{benefit}_{d,c}*\text{locate}_{d,c} -
\sum_{d,c,d2,c2 \in dcd2c2} \text{communicationCost}_{d,c,d2,c2}*y_{d,c,d2,c2}
\end{equation}

This linear integer programming formulation of the decentralization problem is in fact a linearization of a quadratic assignment formulation of this problem. With Gurobi 9.0, you can directly solve  the quadratic assignment formulation of the decentralization problem without the auxiliary variables and the logical constraints.

### Objective Function

**Gross margin**: Maximize the gross margin of relocation.

\begin{equation}
\text{Maximize} \quad Z = \sum_{d \in \text{Departments}} \sum_{c \in \text{Cities}} \text{benefit}_{d,c}*\text{locate}_{d,c} -
\sum_{d,c,d2,c2 \in dcd2c2} \text{communicationCost}_{d,c,d2,c2}*\text{locate}_{d,c}*\text{locate}_{d2,c2}
\end{equation}

### Constraints

**Department location**: Each department must be located in only one city.

\begin{equation}
\sum_{c \in \text{Cities}} \text{locate}_{d,c} = 1 \quad \forall d \in \text{Departments}
\end{equation}

**Departments limit**: No city may be the location for more than three departments.

\begin{equation}
\sum_{d \in \text{Departments}} \text{locate}_{d,c} \leq 3 \quad \forall c \in \text{Cities}
\end{equation}

## Python Implementation

We import the Gurobi Python Module and other Python libraries.


```python
%pip install gurobipy
```


```python
import pandas as pd

import gurobipy as gp
from gurobipy import GRB

# tested with Python 3.7.0 & Gurobi 9.0
```

## Input data  
We define all the input data for the model.


```python
# Lists of deparments and cities

Deparments = ['A','B','C','D','E']
Cities = ['Bristol', 'Brighton', 'London']

# Create a dictionary to capture benefits -in thousands of dollars from relocation.

d2c, benefit = gp.multidict({
    ('A', 'Bristol'): 10,
    ('A', 'Brighton'): 10,
    ('A', 'London'): 0,
    ('B', 'Bristol'): 15,
    ('B', 'Brighton'): 20,
    ('B', 'London'): 0,
    ('C', 'Bristol'): 10,
    ('C', 'Brighton'): 15,
    ('C', 'London'): 0,
    ('D', 'Bristol'): 20,
    ('D', 'Brighton'): 15,
    ('D', 'London'): 0,
    ('E', 'Bristol'): 5,
    ('E', 'Brighton'): 15,
    ('E', 'London'): 0
})

# Create a dictionary to capture the communication costs -in thousands of dollars from relocation.

dcd2c2, communicationCost = gp.multidict({
    ('A','London','C','Bristol'): 13,
    ('A','London','C','Brighton'): 9,
    ('A','London','C','London'): 10,
    ('A','London','D','Bristol'): 19.5,
    ('A','London','D','Brighton'): 13.5,
    ('A','London','D','London'): 15,
    ('B','London','C','Bristol'): 18.2,
    ('B','London','C','Brighton'): 12.6,
    ('B','London','C','London'): 14,
    ('B','London','D','Bristol'): 15.6,
    ('B','London','D','Brighton'): 10.8,
    ('B','London','D','London'): 12,
    ('C','London','E','Bristol'): 26,
    ('C','London','E','Brighton'): 18,
    ('C','London','E','London'): 20,
    ('D','London','E','Bristol'): 9.1,
    ('D','London','E','Brighton'): 6.3,
    ('D','London','E','London'): 7,
    ('A','Bristol','C','Bristol'): 5,
    ('A','Bristol','C','Brighton'): 14,
    ('A','Bristol','C','London'): 13,
    ('A','Bristol','D','Bristol'): 7.5,
    ('A','Bristol','D','Brighton'): 21,
    ('A','Bristol','D','London'): 19.5,
    ('B','Bristol','C','Bristol'): 7,
    ('B','Bristol','C','Brighton'): 19.6,
    ('B','Bristol','C','London'): 18.2,
    ('B','Bristol','D','Bristol'): 6,
    ('B','Bristol','D','Brighton'): 16.8,
    ('B','Bristol','D','London'): 15.6,
    ('C','Bristol','E','Bristol'): 10,
    ('C','Bristol','E','Brighton'): 28,
    ('C','Bristol','E','London'): 26,
    ('D','Bristol','E','Bristol'): 3.5,
    ('D','Bristol','E','Brighton'): 9.8, 
    ('D','Bristol','E','London'): 9.1,
    ('A','Brighton','C','Bristol'): 14,
    ('A','Brighton','C','Brighton'): 5,
    ('A','Brighton','C','London'): 9,
    ('A','Brighton','D','Bristol'): 21,
    ('A','Brighton','D','Brighton'): 7.5,
    ('A','Brighton','D','London'): 13.5,
    ('B','Brighton','C','Bristol'): 19.6,
    ('B','Brighton','C','Brighton'): 7,
    ('B','Brighton','C','London'): 12.6,
    ('B','Brighton','D','Bristol'): 16.8,
    ('B','Brighton','D','Brighton'): 6,
    ('B','Brighton','D','London'): 10.8,
    ('C','Brighton','E','Bristol'): 28,
    ('C','Brighton','E','Brighton'): 10,
    ('C','Brighton','E','London'): 18,
    ('D','Brighton','E','Bristol'): 9.8,
    ('D','Brighton','E','Brighton'): 3.5,
    ('D','Brighton','E','London'): 6.3
})
```

## Model Deployment

We create a model and the variables. These binary decision variables define the city at which each department will be located.

Solving quadratic assignment problems  with Gurobi is as easy as configuring the global parameter `nonConvex`, and setting this parameter to the value of 2.


```python
model = gp.Model('decentralization')

# Set global parameters 
model.params.nonConvex = 2

# locate deparment d at city c
locate = model.addVars(d2c, vtype=GRB.BINARY, name="locate")
```

    Using license file c:\gurobi\gurobi.lic
    Changed value of parameter nonConvex to 2
       Prev: -1  Min: -1  Max: 2  Default: -1


Each department must be located in exactly one city.


```python
# Department location constraint

department_location = model.addConstrs((gp.quicksum(locate[d,c] for c in Cities) == 1 for d in Deparments), 
                                    name='department_location')
```

No city may be the location for more than three departments.


```python
# Limit on number of departments

departments_limit = model.addConstrs((gp.quicksum(locate[d,c] for d in Deparments) <= 3 for c in Cities), 
                                    name='departments_limit')
```

We now set the optimization objective, which is to maximize gross margins.


```python
model.setObjective((gp.quicksum(benefit[d,c]*locate[d,c] for d,c in d2c) 
                    - gp.quicksum(communicationCost[d,c,d2,c2]*locate[d,c]*locate[d2,c2] for d,c,d2,c2 in dcd2c2) ),
                   GRB.MAXIMIZE)
```


```python
# Verify model formulation

model.write('decentralizationQA.lp')

# Run optimization engine

model.optimize()
```

    Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
    Optimize a model with 8 rows, 15 columns and 30 nonzeros
    Model fingerprint: 0x2ad3c449
    Model has 54 quadratic objective terms
    Variable types: 0 continuous, 15 integer (15 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+00]
      Objective range  [5e+00, 2e+01]
      QObjective range [7e+00, 6e+01]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 3e+00]
    Found heuristic solution: objective -73.9000000
    Presolve time: 0.00s
    Presolved: 62 rows, 69 columns, 192 nonzeros
    Variable types: 0 continuous, 69 integer (69 binary)
    
    Root relaxation: objective -6.750000e+01, 14 iterations, 0.00 seconds
    
        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
    
         0     0   67.50000    0   10  -73.90000   67.50000   191%     -    0s
    H    0     0                     -33.9000000   67.50000   299%     -    0s
    H    0     0                     -16.3000000   67.50000   514%     -    0s
    H    0     0                      14.9000000   67.50000   353%     -    0s
         0     0   30.00000    0   22   14.90000   30.00000   101%     -    0s
    
    Cutting planes:
      Gomory: 3
      MIR: 16
      Zero half: 4
      Mod-K: 2
      RLT: 25
    
    Explored 1 nodes (43 simplex iterations) in 0.04 seconds
    Thread count was 8 (of 8 available processors)
    
    Solution count 4: 14.9 -16.3 -33.9 -73.9 
    
    Optimal solution found (tolerance 1.00e-04)
    Best objective 1.490000000000e+01, best bound 1.490000000000e+01, gap 0.0000%


## Analysis

The optimal relocation plan and associated financial report follows.


```python
relocation_plan = pd.DataFrame(columns=["Department", "City"])

count = 0

for c in Cities:
    for d in Deparments:
        if(locate[d,c].x > 0.5):
            count += 1
            relocation_plan = relocation_plan.append({"Department": d, "City": c }, ignore_index=True )
relocation_plan.index=['']*count
relocation_plan
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>Department</th>
      <th>City</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th></th>
      <td>A</td>
      <td>Bristol</td>
    </tr>
    <tr>
      <th></th>
      <td>D</td>
      <td>Bristol</td>
    </tr>
    <tr>
      <th></th>
      <td>B</td>
      <td>Brighton</td>
    </tr>
    <tr>
      <th></th>
      <td>C</td>
      <td>Brighton</td>
    </tr>
    <tr>
      <th></th>
      <td>E</td>
      <td>Brighton</td>
    </tr>
  </tbody>
</table>
</div>




```python
print("\n\n_________________________________________________________________________________")
print(f"Financial report")
print("_________________________________________________________________________________")
total_benefit = 0
for c in Cities:
    for d in Deparments:
        if(locate[d,c].x > 0.5):
            total_benefit += 1000*benefit[d,c]

dollars_benefit = '${:,.2f}'.format(total_benefit)
print(f"The yearly total benefit is {dollars_benefit} dollars")

total_communication_cost = 0
for d,c,d2,c2 in dcd2c2:
    if(locate[d,c].x*locate[d2,c2].x > 0.5):
        total_communication_cost += 1000*communicationCost[d,c,d2,c2]

dollars_communication_cost = '${:,.2f}'.format(total_communication_cost)
print(f"The yearly total communication cost is {dollars_communication_cost} dollars")

total_gross_margin = total_benefit - total_communication_cost
dollars_gross_margin = '${:,.2f}'.format(total_gross_margin)
print(f"The yearly total gross margin is {dollars_gross_margin} dollars")
```

    
    
    _________________________________________________________________________________
    Financial report
    _________________________________________________________________________________
    The yearly total benefit is $80,000.00 dollars
    The yearly total communication cost is $65,100.00 dollars
    The yearly total gross margin is $14,900.00 dollars


## References

H. Paul Williams, Model Building in Mathematical Programming, fifth edition.

Copyright © 2020 Gurobi Optimization, LLC

b891e4bc9a482e5970725cb47dae298669513586
ipynb
Jupyter Notebook
decentralization_planning/decentralization_planning_gcl.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2019-07-11T15:08:37.000Z
2022-03-25T10:12:54.000Z
decentralization_planning/decentralization_planning_gcl.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2020-10-29T12:34:13.000Z
2022-02-28T14:16:43.000Z
decentralization_planning/decentralization_planning_gcl.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2019-11-11T17:04:54.000Z
2022-03-30T21:34:20.000Z
Qwen/Qwen-72B
1. YES
2. YES