# Assignment Problem

A fundamental combinatorial optimization problem.

- $n$ tasks to be done
- $n$ workers to do the tasks
- Each worker has a certain cost for each task ($c_{ij}$)

Problem: Find the best assignment of all tasks that minimizes the total cost.

Constraints:
* Each worker can do at most one task
* All tasks need to be done

# Mathematical Formulation

\begin{align}
\text{minimize} & \sum_{i = 1}^{n}\sum_{j = 1}^{n} c_{ij}x_{ij}, \\
\text{subject to} & \\
& \sum_{i = 1}^{n} x_{ij} \leq 1 & \forall j = 1, ..., n & \ \ \textit{ (workload)},\\
& \sum_{j = 1}^{n} x_{ij} = 1 & \forall i = 1, ..., n & \ \ \textit{ (task completion)}, \\
& x_{ij} \in \{0,1\} & \forall i,j = 1, ..., n
\end{align}

where $x_{ij}$ is 1 if worker $i$ performs task $j$, 0 otherwise.

We can replace the integrality constraints with continuous constraints. The solution will not change as the constraint matrix is totally unimodular.

# Coding in Python using gurobipy
## Step 1: Creating input data (cost matrix)


```python
import numpy as np
cost = np.random.randint(1, 10, (4,4))
```

## Step 2: Importing gurobipy package


```python
from gurobipy import Model, GRB
```

## Step 3: Creating the model


```python
assignment_model = Model('Assignment')
```

## Step 4: Creating decision variables


```python
x = assignment_model.addVars(cost.shape[0], 
                            cost.shape[1], 
                            vtype = GRB.BINARY, 
                            name = "x")
```

## Step 5: Adding the constraints
\begin{align}
\sum_{i = 1}^{n} x_{ij} \leq 1 &\qquad \forall j = 1, ..., n & \ \ \textit{ (workload)},\\
\sum_{j = 1}^{n} x_{ij} = 1 & \qquad \forall i = 1, ..., n & \ \ \textit{ (task completion)}.
\end{align}


```python
# sum_{i = 1}^{n} x_{ij} <= 1 for all j
assignment_model.addConstrs((sum(x[i,j] for i in range(cost.shape[0])) <= 1 
                             for j in range(cost.shape[1])), 
                            name = 'work_load')

# sum_{j = 1}^{n} x_{ij}  = 1 for all i
assignment_model.addConstrs((sum(x[i,j] for j in range(cost.shape[1])) == 1 
                             for i in range(cost.shape[0])),
                            name = 'task_completion')
```




    {0: <gurobi.Constr *Awaiting Model Update*>,
     1: <gurobi.Constr *Awaiting Model Update*>,
     2: <gurobi.Constr *Awaiting Model Update*>,
     3: <gurobi.Constr *Awaiting Model Update*>}



## Step 6: Defining the objective function
$$\sum_{i = 1}^{n}\sum_{j = 1}^{n} c_{ij}x_{ij}$$


```python
obj_fn = sum(cost[i,j]*x[i,j] for i in range(cost.shape[0]) for j in range(cost.shape[1]))

assignment_model.setObjective(obj_fn, GRB.MINIMIZE)
```

## Step 7: Solve and inspect the model


```python
assignment_model.setParam('OutputFlag', False)
assignment_model.optimize()

print('Model Statistics')
assignment_model.printStats()
print('\n\nModel Output\n')
print(assignment_model.display())
```

    Model Statistics
    
    Statistics for model Assignment :
      Linear constraint matrix    : 8 Constrs, 16 Vars, 32 NZs
      Variable types              : 0 Continuous, 16 Integer (16 Binary)
      Matrix coefficient range    : [ 1, 1 ]
      Objective coefficient range : [ 1, 9 ]
      Variable bound range        : [ 1, 1 ]
      RHS coefficient range       : [ 1, 1 ]
    
    
    Model Output
    
    Minimize
       <gurobi.LinExpr: 2.0 x[0,0] + 3.0 x[0,1] + 6.0 x[0,2] + 3.0 x[0,3] + 3.0 x[1,0] + 9.0 x[1,1] + 9.0 x[1,2] + x[1,3] + x[2,0] + x[2,1] + 8.0 x[2,2] + 3.0 x[2,3] + 7.0 x[3,0] + 2.0 x[3,1] + 9.0 x[3,2] + 4.0 x[3,3]>
    Subject To
       work_load[0] : <gurobi.LinExpr: x[0,0] + x[1,0] + x[2,0] + x[3,0]> <= 1.0
       work_load[1] : <gurobi.LinExpr: x[0,1] + x[1,1] + x[2,1] + x[3,1]> <= 1.0
       work_load[2] : <gurobi.LinExpr: x[0,2] + x[1,2] + x[2,2] + x[3,2]> <= 1.0
       work_load[3] : <gurobi.LinExpr: x[0,3] + x[1,3] + x[2,3] + x[3,3]> <= 1.0
       task_completion[0] : <gurobi.LinExpr: x[0,0] + x[0,1] + x[0,2] + x[0,3]> = 1.0
       task_completion[1] : <gurobi.LinExpr: x[1,0] + x[1,1] + x[1,2] + x[1,3]> = 1.0
       task_completion[2] : <gurobi.LinExpr: x[2,0] + x[2,1] + x[2,2] + x[2,3]> = 1.0
       task_completion[3] : <gurobi.LinExpr: x[3,0] + x[3,1] + x[3,2] + x[3,3]> = 1.0
    Binaries
       ['x[0,0]', 'x[0,1]', 'x[0,2]', 'x[0,3]', 'x[1,0]', 'x[1,1]', 'x[1,2]', 'x[1,3]', 'x[2,0]', 'x[2,1]', 'x[2,2]', 'x[2,3]', 'x[3,0]', 'x[3,1]', 'x[3,2]', 'x[3,3]']
    None


## Output the solution


```python
print('Optimization is done. Objective Function Value: %.2f' % assignment_model.objVal)

# Get values of the decision variables
for v in assignment_model.getVars():
    if v.x > 0:
        print('%s: %g' % (v.varName, v.x))
```

    Optimization is done. Objective Function Value: 10.00
    x[0,2]: 1
    x[1,3]: 1
    x[2,0]: 1
    x[3,1]: 1


# Relaxing the binary constraint


```python
assignment_model_2 = Model('Assignment_2')

y = assignment_model_2.addVars(cost.shape[0], 
                               cost.shape[1],
                               vtype = GRB.CONTINUOUS,
                               lb = 0, ub = 1, 
                               name = "x")

# sum_{i = 1}^{n} y_{ij} <= 1 for all j
assignment_model_2.addConstrs((sum(y[i,j] for i in range(cost.shape[0])) == 1 
                               for j in range(cost.shape[1])), 
                              name = 'work_load')

# sum_{j = 1}^{n} y_{ij}  = 1 for all i
assignment_model_2.addConstrs((sum(y[i,j] for j in range(cost.shape[1])) == 1 
                               for i in range(cost.shape[0])),
                              name = 'task_completion')

obj_fn = sum(cost[i,j]*y[i,j] for i in range(cost.shape[0]) for j in range(cost.shape[1]))
assignment_model_2.setObjective(obj_fn, GRB.MINIMIZE)

assignment_model_2.setParam('OutputFlag', False)

assignment_model_2.optimize()

print('Optimization is done. Objective Function Value: %.2f' % assignment_model_2.objVal)

# Get values of the decision variables
for v in assignment_model.getVars():
    if v.x > 0:
        print('%s: %g' % (v.varName, v.x))
```

    Optimization is done. Objective Function Value: 10.00
    x[0,2]: 1
    x[1,3]: 1
    x[2,0]: 1
    x[3,1]: 1



```python

```

66ade79b30e6a10e991e17a20563ea18d99109dd
ipynb
Jupyter Notebook
mathematicalProgramming/Video11/11_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video11/11_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video11/11_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
2021-11-21T05:02:50.000Z
2022-02-17T04:44:57.000Z
Qwen/Qwen-72B
1. YES
2. YES