Lab 4 - Assignment Problems and Shortest Path
1. Introduction
This lab introduces two important network optimization models:
- Assignment Problems
- Shortest Path Problems
Topics covered include:
- Machineco Assignment Problem
- Mathematical formulation of assignment problems
- General shortest path model
- Seervada Park shortest path example
2. Assignment Problem
The assignment problem seeks to assign resources to tasks while minimizing cost or maximizing effectiveness.
Common applications include:
- Assigning workers to jobs
- Assigning machines to tasks
- Assigning vehicles to routes
- Assigning students to projects
The assignment problem is a special case of the transportation problem where:
- Each source has supply equal to 1
- Each destination has demand equal to 1
- Decision variables are binary
3. Machineco Assignment Problem
Machineco has four machines and four jobs.
Each machine must be assigned to exactly one job, and each job must be assigned to exactly one machine.
The setup times (hours) are given below.
| Machine | Job 1 | Job 2 | Job 3 | Job 4 |
|---|---|---|---|---|
| Machine 1 | 14 | 5 | 8 | 7 |
| Machine 2 | 2 | 12 | 6 | 5 |
| Machine 3 | 7 | 8 | 3 | 9 |
| Machine 4 | 2 | 4 | 6 | 10 |
Objective: Minimize total setup time.
4. Assignment Problem Mathematical Model
Decision Variables
\[ x_{ij} = \begin{cases} 1 & \text{if machine } i \text{ is assigned to job } j\\ 0 & \text{otherwise} \end{cases} \]
Objective Function
Minimize total setup time:
\[ \min Z = \sum_{i=1}^{4} \sum_{j=1}^{4} c_{ij}x_{ij} \]
where:
- \(c_{ij}\) = setup time for assigning machine \(i\) to job \(j\)
Constraints
Each Machine Assigned Exactly Once
\[ \sum_{j=1}^{4} x_{ij} = 1 \qquad \forall i = 1,2,3,4 \]
Each machine must receive exactly one assignment.
Each Job Assigned Exactly Once
\[ \sum_{i=1}^{4} x_{ij} = 1 \qquad \forall j = 1,2,3,4 \]
Each job must be assigned to exactly one machine.
Binary Constraints
\[ x_{ij}\in\{0,1\} \]
5. Shortest Path Problem
The shortest path problem seeks the minimum-cost path between two nodes in a network.
Applications include:
- Transportation routing
- Logistics planning
- Telecommunications
- Project scheduling
- GPS navigation systems
A network consists of:
- Nodes (vertices)
- Arcs (edges)
- Arc costs (distance, time, cost, etc.)
6. General Shortest Path Model
Decision Variables
\[ x_{ij} = \begin{cases} 1 & \text{if arc } (i,j) \text{ is selected}\\ 0 & \text{otherwise} \end{cases} \]
Objective Function
Minimize total path cost:
\[ \min Z = \sum_{(i,j)\in A} c_{ij}x_{ij} \]
where:
- \(A\) = set of arcs
- \(c_{ij}\) = cost of arc \((i,j)\)
Flow Conservation Constraints
For every node:
\[ \sum_{j:(i,j)\in A} x_{ij} - \sum_{j:(j,i)\in A} x_{ji} = \begin{cases} 1 & \text{if } i = \text{source}\\ -1 & \text{if } i = \text{destination}\\ 0 & \text{otherwise} \end{cases} \]
Interpretation:
- One unit of flow leaves the source.
- One unit of flow enters the destination.
- Intermediate nodes conserve flow.
Binary Constraints
\[ x_{ij}\in\{0,1\} \]
7. Seervada Park Example
Seervada Park wants to determine the shortest path between an origin node and a destination node.
Network Diagram
Each arc represents a possible route with an associated distance.
Goal: Find the shortest path from node \(O\) (origin) to node \(T\) (destination).
8. Seervada Mathematical Model
Decision Variables
\[ x_{ij} = \begin{cases} 1 & \text{if arc } (i,j) \text{ is used}\\ 0 & \text{otherwise} \end{cases} \]
Objective Function
\[ \min Z = \sum c_{ij}x_{ij} \]
where:
- \(c_{ij}\) is the distance associated with arc \((i,j)\).
9. Seervada Flow Constraints
Origin Node
\[ \sum_j x_{Oj} - \sum_j x_{jO} = 1 \]
One unit of flow must leave the origin.
Destination Node
\[ \sum_j x_{jT} - \sum_j x_{Tj} = 1 \]
One unit of flow must arrive at the destination.
Intermediate Nodes
For nodes \(A\), \(B\), \(C\), \(D\), and \(E\):
\[ \sum_j x_{ij} - \sum_j x_{ji} = 0 \]
Flow entering a node must equal flow leaving that node.
Binary Constraints
\[ x_{ij}\in\{0,1\} \]
View Slides
Materials
- Excel File
- Follow Along
- Completed
- Google Colab
- Follow Along
- Completed
- GAMS Code
References
Winston, W. L. (2004). Operations Research: Applications and Algorithms (4th ed.). Thomson Brooks/Cole.
Acar, Y. Network Optimization Lecture Notes.
PuLP Documentation. https://coin-or.github.io/pulp/