MATH1058 Honours Foundation of Modern Mathematics Coursework: Simplex Method
1 Coursework
instructions
March 12, 2024
This coursework is linked to the Simplex Method. In theory the worst case complexity of the Simplex Method is 𝒪(𝑛!). That is, the computational cost grows factorially with the number of decision variables. However, in practical cases the complexity is often much less. Here we will study how much less.
You will
-
code, in Python, alternative pivoting rules for the Simplex Method;
-
run the different rules on multiple different linear programs with different numbers of decision
variables, outputting the run-time data as an Excel spreadsheet;
-
within Excel, compute the average and worst case run-time as a function of the instance size;
-
within Excel, produce plots showing (quantitatively) the complexity;
-
within LaTeX, write a report analysing the pivoting rules, including your analysis using tables
and plots.
1.1 Algorithms
The Simplex Method performs pivoting operations swapping an index between the basic set 𝐵
and its complement 𝑁. The pivoting rule chooses a (row, column) pair (𝑟,𝑠). Given that pivot
entry, row operations are performed so that the tableau entry 𝑎̄ → 1, and all other entries in that 𝑟𝑠
column,𝑎̄ ,𝑖≠𝑟→0. 𝑖𝑠
In the theory part of the course the pivoting rule shown was Bland’s rule, also called the smallest
subscript rule. This first chooses 𝑠 to be the smallest (column) index with negative reduced costs
𝑐̄ < 0. The rule next chooses 𝑟 to be the smallest (row) index that satisfies the minimum ratio 𝑠
test.
1.1.1 Largest subscript rule
Symmetry suggests there should be nothing special about using the smallest subscript. A first guess suggests that using the largest subscript should work just as well.
In the largest subscript rule, we first choose 𝑠 to the the largest column index with negative reduced costs. The rule next chooses 𝑟 to be the largest row index that satisfies the minimum ratio test.
1.1.2 Largest change rule
Once we have found the pivot index (𝑟, 𝑠) the simplex method uses row operations to add a multiple
of row 𝑟 to row 0 containing the reduced costs and objective function, in order to set 𝑐 ̄ → 0. This 𝑠
1
changes the objective function by an amount 𝑐̄ 𝑎̄ /𝑎̄ = 𝑐̄ 𝜃∗, where 𝜃∗ is the result of the minimum 𝑠𝑟0𝑟𝑠𝑠𝑠 𝑠
ratio test for this particular column 𝑠. We could consider all possible columns with negative reduced costs and consider the best, or worse, impacts on the objective function. Here we consider the largest possible change. The question is whether the additional work we apparently have to do for this rule is compensated by the best possible increase in the objective function.
In the largest change rule, we first choose 𝑠 to be the column index that changes the objective function by the largest amount Δ = max𝑠 Δ𝑠, where in column 𝑠 the change is
𝑎̄ Δ=𝑐̄min 𝑟0=𝑐̄𝜃∗.
𝑠 𝑠𝑟∶𝑎̄ >0𝑎̄ 𝑠𝑠
𝑟𝑠
If multiple columns have the same change, choose the smallest index. The row index 𝑟 is chosen to
be the smallest index that satisfies the minimum ratio test for the chosen row 𝑠.
1.2 Python
On Noteable you will find code implementing the (one phase) Simplex Method and Bland’s rule.
The function simplex takes as input the tableau (in basic form), the initial basis (as a list of integer indexes), and a function that implements the pivoting rule. It returns the solution as a dictionary containing its status (did it succeed), the optimal solution, and the final basis. This function is defined in the simplex_generation.py file: you should not modify it.
The function find_pivot_bland implements Bland’s rule. It takes as input the tableau, and returns the (r, s) pair giving the row and column indexes on which to pivot. This function is defined in the simplex.ipynb notebook. You should not modify this function, but you will need to edit code later in this notebook.
1.2.1 Task 1
At the top of the file there is an integer variable
student_id = 12345678
You must replace this number with your own eight digit ID. This is used to generate the problems the Simplex Method will solve.
1.2.2 Task 2
Using find_pivot_bland as a template, you should implement find_pivot_largest_subscript and find_pivot_smallest_change. This should be done within the simplex.ipynb notebook. Function stubs are given. The functions should implement the largest subscript rule and the smallest change rule given above.
There are tests on within the notebook that perform very basic checks of the code: they do not guarantee complete correctness.
1.2.3 Task 3
It is essential that you complete task 1 before doing this step.
In the Settings section of the notebook there is a boolean variable set, as
2
𝑟𝑠
run_timings = False
Once you are happy with your code, change this to
run_timings = True
When you run the full notebook, particularly the last cell, it will produce a spreadsheet. This should take no more than one minute (on Noteable: times will vary on other machines). At the end it will have produced an Excel spreadsheet timings.xlsx.
Note: if you cannot complete task 2, or want to continue on with the analysis before completing it, in the Settings section of the notebook there are boolean variables
time_largest_subscript = True time_largest_change = True
By setting the appropriate variable to, for example,
time_largest_subscript = False
a spreadsheet creating the timing data without using that pivoting rule will be produced.
1.3 Excel
The timing data in the Excel spreadsheet was created by looping over a range of problem sizes (quantified by the number of decision variables n; the number of constraints was set to n+5). For each problem size, 50 instances were created. For each instance the simplex method was run using both Bland’s rule and the largest coefficient rule.
The spreadsheet contains two sheets associated with the two pivoting rules. On each sheet, each row contains the times to solve each individual instance. The first column gives the instance size; the next 50 columns gives the times.
1.3.1 Task 4
Download the spreadsheet from Noteable. Duplicate it and rename it analysis.xlsx. Load the duplicate analysis.xlsx into Excel. Create a new sheet in the workbook; call it Analysis.
Using appropriate Excel functions, add seven columns to this sheet. The first should contain the instance sizes n. The next six should contain the average time and worst-case time for each pivoting rule and instance size (Smallestsubscript: Average, Largestsubscript:Average, Largestchange:Average, Smallestsubscript: Worst, Largest subscript: Worst, Largest change: Worst).
From these, create seven more columns containing the logarithms (base 10) of n and each time respectively.
1.3.2 Task 5
Create two plots. One should plot the (logarithm of the) average run time for each pivoting rule as a function of the (logarithm of the) instance size. The other should plot the (logarithm of the) worst case run time for each pivoting rule as a function of the (logarithm of the) instance size. Both plots should be appropriately labelled and include trend lines for each pivoting rule.
Save your figures in pdf or png format (pdf is preferred where possible). 3
1.3.3 Task 6
Using appropriate functions (e.g., INTERCEPT, SLOPE), compute the best fit coefficients for log(𝑡) = 𝑝0 log(𝑛) + 𝑝1,
where 𝑡 is the timing data and 𝑛 is the instance sizes. There should be different coefficients for each pivoting rule and for the average and worst cases (so six pairs of coefficients in total).
1.4 LaTeX
On Overleaf there is a report template. The report template can be found here. From the Overleaf menu (top left) you can Copy Project to your account so you can edit your personal version. You need to complete the report to communicate your results.
1.4.1 Task 7
In the first section of the LaTeX document, include your Python code for the functions find_pivot_largest_subscript and find_pivot_largest_change.
1.4.2 Task 8
In the second section of the LaTeX document, using big 𝒪 notation, analyse your Python codes. 1.4.3 Task 9
In the third section of your LaTeX document, include the figures created in Excel. Add captions explaining what each is.
Also in the third section, add a table reporting the 𝑝0,1 coefficients computed in task 6. 1.4.4 Task 10
In the fourth and final section of the LaTeX document, write one paragraph to explain which of the pivoting rules is more efficient in which cases. You should use the results from the complexity analysis in task 8, and your figures and table in task 9, to back up your statements.
1.5 Submission
All work should be submitted through Blackboard.
The notebook should also be submitted through Noteable. Before submitting through Noteable,
ensure that the boolean variable is reset, so run_timings = False. Five “things” need submitting.
-
Thesimplex.ipynbnotebook.
-
The (unmodified) timings.xlsx spreadsheet created by simplex.ipynb.
-
The Excel spreadsheet with the completed analysis, analysis.xlsx.
-
All LaTeX and figure files needed to create the report, as a zip file. If Overleaf was used,
go to the Menu (top left), and from Download select Source. This zip file should contain
everything needed.
-
The report as a pdf file. If Overleaf was used, go the the Menu (top left), and from Download
select PDF.
4
1.6 Marking scheme (rough)
• [8 marks] Python code runs correctly
• [2 marks] Python code documented correctly
• [4 marks] Excel data analysis organised correctly
• [4 marks] Excel figures created, labelled, with trend lines, correctly
• [2 marks] Intercept and slope used correctly
• [4 marks] LaTeX document compiles without errors
• [2 marks] Python code reported in document
• [5 marks] Complexity analysis correct
• [2 marks] Figures included correctly, with captions
• [2 marks] Table created correctly, with caption
• [5 marks] Efficiency argument reasonable, supported by evidence
5
