Quarter: Winter 2025
In this project we ran a numerical experiment to study how the simplex method, an algorithm for solving linear programming problems (finding the optimal value of a linear function subject to a set of inequality constraints), scales with problem size. We generated 500 random linear programs and solved each using Python's scipy library, then used scatter plots to analyze how the number of iterations grows with various measures of problem size.
Each linear program consists of:
- An m×n constraint matrix A (m rows, n columns), where m is the number of constraints and n is the number of variables
- A vector b (length m) giving the right-hand side of each constraint, so the constraints take the form
$Ax \leq b$ - A vector c (length n) giving the coefficients of the objective function being maximized
| File | Description |
|---|---|
335Assignment1.py |
Generates 500 random linear programs and solves each using scipy's simplex implementation. Contains commented-out scatter plot blocks for each of the five analysis questions. |
figures/ |
Output plots from the analysis runs. |
Question 1: Does the growth in m+n correspond to a growth in the number of iterations? If so, is this linear? Exponential?
Graphing this relationship using a scatter plot shows that this is clearly the case, with the growth appearing to be of exponential nature.
Question 2: Does the growth in m correspond to a growth in the number of iterations? If so, is this linear? Exponential?
The results are nearly identical to those of Question 1. The graph demonstrates a clear exponential growth in iterations as m (the number of constraints) grows.
Question 3: How does the number of iterations depend on min(m, n)? Is this linear? Exponential?
Here we look at the smaller of the two dimensions (number of constraints m vs. number of variables n) rather than either one individually. While we still see growth in iterations corresponding to growth of the smallest dimension, it is questionable whether the growth could even be considered exponential. The graph can be interpreted as demonstrating very slow exponential growth, or as growing at an approximately linear pace.
Question 4: Is it much faster to solve an unbounded problem than a bounded problem?
A bounded problem is one where the simplex method finds an optimal solution. An unbounded problem is one where no finite optimum exists, meaning the objective function can be improved indefinitely. To compare, we again plot m+n against iteration count, this time coloring points by whether the problem was bounded or unbounded.
The results clearly show that generally unbounded problems are faster to solve than their bounded counterparts. For the 500 generated problems the average iterations were:
- Unbounded problems: ~108.27 iterations
- Bounded problems: ~238.98 iterations
Bounded problems on average are about twice as slow to solve. It is interesting to note that graphically, on occasion there are some exceptions to this observation.
Question 5: Is an m×n problem faster to solve than an n×m problem when m >> n?
This question asks whether swapping the dimensions of the constraint matrix (transposing A, so that the number of rows and columns are exchanged) affects how many iterations the simplex method needs. The total number of entries in A stays the same (m×n), but the shape of the problem changes.
For each of the 500 problems, the transpose of A was taken and the b and c vectors were regenerated using the same random seed to keep as many factors consistent as possible. The results were then compared over an x-axis of problem size (m×n).
Graphically showing how problems compare to their transposed version produces noisy results that don't feel appropriate to draw any strong conclusions from. In an attempt to reach further clarity, rather than plotting iterations directly, the ratio of transpose iterations to original iterations was calculated for each problem. A ratio greater than 1 means the transposed problem required more iterations; a ratio less than 1 means it required fewer.
This data seems to suggest that as the size of a problem grows, the likelihood of the transposed problem being drastically slower is reduced. The following are average ratio values across different ranges of problem size (m×n):
| Problem size (m×n) | Average ratio (transpose / original) |
|---|---|
| 0 to 1000 | 2.62 |
| 1000 to 2000 | 2.18 |
| 2000 to 3000 | 1.61 |
| 3000 to 4000 | 1.53 |
| 4000 to 5000 | 1.03 |
This would seem to indicate that the transposed problem is significantly slower than the original for smaller problems, but trends to require an equal number of iterations as the size of the problem grows.
Requires Python with numpy, scipy, and matplotlib.
python 335Assignment1.pyEach scatter plot block is commented out by default. Uncomment the block for the question you want to plot before running.