# 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 docplex
## Step 1: Creating input data (cost matrix)


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

## Step 2: Importing docplex package


```python
from docplex.mp.model import Model
```

## Step 3: Creating the model


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

## Step 4: Creating decision variables


```python
x = assignment_model.binary_var_matrix(cost.shape[0], 
                                       cost.shape[1], 
                                       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.add_constraints((sum(x[i,j] for i in range(cost.shape[0])) <= 1 
                                  for j in range(cost.shape[1])), 
                                 names = 'work_load')

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




    [docplex.mp.LinearConstraint[task_completion1](x_0_0+x_0_1+x_0_2+x_0_3,EQ,1),
     docplex.mp.LinearConstraint[task_completion2](x_1_0+x_1_1+x_1_2+x_1_3,EQ,1),
     docplex.mp.LinearConstraint[task_completion3](x_2_0+x_2_1+x_2_2+x_2_3,EQ,1),
     docplex.mp.LinearConstraint[task_completion4](x_3_0+x_3_1+x_3_2+x_3_3,EQ,1)]



## 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.set_objective('min',obj_fn)

assignment_model.print_information()
```

    Model: Assignment
     - number of variables: 16
       - binary=16, integer=0, continuous=0
     - number of constraints: 8
       - linear=8
     - parameters: defaults
     - objective: minimize
     - problem type is: MILP


## Inspect model by printing


```python
print(assignment_model.export_as_lp_string())
```

    \ This file has been generated by DOcplex
    \ ENCODING=ISO-8859-1
    \Problem name: Assignment
    
    Minimize
     obj: 6 x_0_0 + 7 x_0_1 + 5 x_0_2 + 8 x_0_3 + 6 x_1_0 + 7 x_1_1 + 2 x_1_2
          + 2 x_1_3 + 2 x_2_0 + x_2_1 + 2 x_2_2 + 7 x_2_3 + x_3_0 + x_3_1 + 8 x_3_2
          + x_3_3
    Subject To
     work_load1: x_0_0 + x_1_0 + x_2_0 + x_3_0 <= 1
     work_load2: x_0_1 + x_1_1 + x_2_1 + x_3_1 <= 1
     work_load3: x_0_2 + x_1_2 + x_2_2 + x_3_2 <= 1
     work_load4: x_0_3 + x_1_3 + x_2_3 + x_3_3 <= 1
     task_completion1: x_0_0 + x_0_1 + x_0_2 + x_0_3 = 1
     task_completion2: x_1_0 + x_1_1 + x_1_2 + x_1_3 = 1
     task_completion3: x_2_0 + x_2_1 + x_2_2 + x_2_3 = 1
     task_completion4: x_3_0 + x_3_1 + x_3_2 + x_3_3 = 1
    
    Bounds
     0 <= x_0_0 <= 1
     0 <= x_0_1 <= 1
     0 <= x_0_2 <= 1
     0 <= x_0_3 <= 1
     0 <= x_1_0 <= 1
     0 <= x_1_1 <= 1
     0 <= x_1_2 <= 1
     0 <= x_1_3 <= 1
     0 <= x_2_0 <= 1
     0 <= x_2_1 <= 1
     0 <= x_2_2 <= 1
     0 <= x_2_3 <= 1
     0 <= x_3_0 <= 1
     0 <= x_3_1 <= 1
     0 <= x_3_2 <= 1
     0 <= x_3_3 <= 1
    
    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
    End
    


## Step 7: Solve the model and output the solution


```python
assignment_model.solve()

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

# Get values of the decision variables
assignment_model.print_solution()
```

    Optimization is done. Objective Function Value: 9.00
    objective: 9
      x_0_2=1
      x_1_3=1
      x_2_1=1
      x_3_0=1


# Relaxing the binary constraint


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

y = assignment_model_2.continuous_var_matrix(cost.shape[0], 
                                             cost.shape[1], 
                                             lb = 0, ub = 1, 
                                             name="x")

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

# sum_{j = 1}^{n} y_{ij}  = 1 for all i
assignment_model_2.add_constraints((sum(y[i,j] for j in range(cost.shape[1])) == 1 
                                    for i in range(cost.shape[0])),
                                  names = '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.set_objective('min', obj_fn)

assignment_model_2.solve()

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

# Get values of the decision variables
assignment_model_2.print_solution()
```

    Optimization is done. Objective Function Value: 9.00
    objective: 9.000
      x_0_2=1.000
      x_1_3=1.000
      x_2_1=1.000
      x_3_0=1.000



```python

```

f5c6d97eea7a2cabd8dfab3404b17a99a2ae6d36
ipynb
Jupyter Notebook
mathematicalProgramming/Video10/10_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video10/10_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video10/10_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