Lab 3 - Assignment and Transportation Problems
1. Introduction
This lab introduces transportation and assignment problems, two important classes of optimization models.
Topics covered include:
- Transportation Problems
- Assignment Problems
- Powerco Transportation Example
- Decision Variables with
LpVariable.dicts() - Useful Pandas Concepts for Optimization
2. Recap: Transportation and Assignment Problems
The Assignment Problem is a special case of the Transportation Problem.
Key characteristics:
- Assignment problems typically have many zero-valued technical coefficients, allowing specialized solution methods.
- Transportation problems represent a many-to-many (m:n) matching problem.
- They are modeled as bipartite networks connecting sources and destinations.
- Common applications involve shipping products from factories to customers or regions.
- The objective is usually to minimize total transportation cost while satisfying supply and demand requirements.
3. Transportation Problem: Closed Form Model
Decision Variables
\[ x_{ij} = \text{amount shipped from source } i \text{ to destination } j \]
Parameters
- \(c_{ij}\) = transportation cost from source \(i\) to destination \(j\)
- \(s_i\) = supply available at source \(i\)
- \(d_j\) = demand required at destination \(j\)
Objective Function
\[ \min \sum_i \sum_j c_{ij}x_{ij} \]
Constraints
Supply Constraints
\[ \sum_j x_{ij} \le s_i \qquad \forall i \]
Demand Constraints
\[ \sum_i x_{ij} \ge d_j \qquad \forall j \]
Non-negativity
\[ x_{ij} \ge 0 \qquad \forall i,j \]
4. Powerco Transportation Problem
Powerco operates three electric power plants that supply electricity to four cities.
Plant Capacities (Million kWh)
| Plant | Supply |
|---|---|
| Plant 1 | 35 |
| Plant 2 | 50 |
| Plant 3 | 40 |
City Demands (Million kWh)
| City | Demand |
|---|---|
| City 1 | 45 |
| City 2 | 20 |
| City 3 | 30 |
| City 4 | 30 |
The objective is to determine the amount of electricity shipped from each plant to each city while minimizing transmission costs.
Transportation Tableau
| Plant | City 1 | City 2 | City 3 | City 4 | Supply |
|---|---|---|---|---|---|
| Plant 1 | $8 | $6 | $10 | $9 | 35 |
| Plant 2 | $9 | $12 | $13 | $7 | 50 |
| Plant 3 | $14 | $9 | $16 | $5 | 40 |
| Demand | 45 | 20 | 30 | 30 | 125 |
All costs are per one million kWh.
5. Open Form Linear Programming Model
Decision Variables
\[ x_{ij} = \text{amount shipped from Plant } i \text{ to City } j \]
Objective Function
\[ \begin{aligned} \min Z = &8x_{11}+6x_{12}+10x_{13}+9x_{14}\\ &+9x_{21}+12x_{22}+13x_{23}+7x_{24}\\ &+14x_{31}+9x_{32}+16x_{33}+5x_{34} \end{aligned} \]
Supply Constraints
\[ x_{11}+x_{12}+x_{13}+x_{14}\le35 \]
\[ x_{21}+x_{22}+x_{23}+x_{24}\le50 \]
\[ x_{31}+x_{32}+x_{33}+x_{34}\le40 \]
Demand Constraints
\[ x_{11}+x_{21}+x_{31}\ge45 \]
\[ x_{12}+x_{22}+x_{32}\ge20 \]
\[ x_{13}+x_{23}+x_{33}\ge30 \]
\[ x_{14}+x_{24}+x_{34}\ge30 \]
Non-negativity
\[ x_{ij}\ge0 \qquad \forall i,j \]
6. PuLP: LpVariable.dicts
In transportation problems, a decision variable is needed for every source-destination pair.
Instead of creating variables individually, PuLP allows variables to be created using indexed dictionaries.
Example
import pulp
plants = [1, 2, 3]
cities = [1, 2, 3, 4]
x = pulp.LpVariable.dicts(
"ship",
[(i, j) for i in plants for j in cities],
lowBound=0,
cat="Continuous"
)This creates variables such as:
\[ x_{11}, x_{12}, x_{13}, \ldots, x_{34} \]
which can be referenced as:
x[(i, j)]Benefits:
- Compact code
- Easy indexing
- Direct correspondence with mathematical notation
- Scales well to large optimization models
7. Pandas Concepts for Data Handling
Optimization models often use external datasets stored in CSV files.
CSV Files
A CSV (Comma-Separated Values) file:
- Stores tabular data
- Can be opened in Excel
- Is widely used for optimization inputs
Example:
Plant,City,Cost
1,1,8
1,2,6
2,1,9DataFrames
A Pandas DataFrame is a two-dimensional table structure.
Features:
- Rows and columns
- Labeled data
- Efficient filtering and manipulation
- Similar to spreadsheets and database tables
Example:
import pandas as pd
df = pd.read_csv("transportation_costs.csv")Index-Based Selection with iloc
The iloc function selects rows and columns by position.
Example:
df.iloc[0]Returns the first row.
df.iloc[0, 2]Returns the value in row 1, column 3.
This is useful when optimization data is stored in matrix form and positions are known.
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. Transportation Problem Lecture Notes.
PuLP Documentation. https://coin-or.github.io/pulp/
Pandas Documentation. https://pandas.pydata.org/