Coursework: Simplex Generation
Coursework
This coursework is linked to the Simplex Method. In theory the worst case complexity of theSimplex Method is𝒪(𝑛!). That is, the computational cost grows factorially with the number ofdecision variables. However, in practical cases the complexity is often much less. Here we will studyhow much less.You will1.code, in Python, alternative pivoting rules for the Simplex Method;2.run the different rules on multiple different linear programs with different numbers of decisionvariables, outputting the run-time data as an Excel spreadsheet;3.within Excel, compute the average and worst case run-time as a function of the instance size;4.within Excel, produce plots showing (quantitatively) the complexity;5.within LaTeX, write a report analysing the pivoting rules, including your analysis using tablesand plots.1.1 AlgorithmsThe 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 pivotentry, row operations are performed so that the tableau entrȳ𝑎𝑟𝑠→1, and all other entries in thatcolumn,̄𝑎𝑖𝑠,𝑖≠𝑟→0.In the theory part of the course the pivoting rule shown wasBland’s rule, also called thesmallestsubscriptrule. 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 ratiotest.1.1.1 Largest coefficient ruleIn thelargest coefficient rule, we look at every column𝑗with negative reduced costs̄𝑐𝑗<0.W ethen choose𝑠to be the column index with largest (in magnitude) negative coefficient.1.2 PythonOn Noteable you will find code implementing the (one phase) Simplex Method and Bland’s rule.The functionsimplextakes as input the tableau (in basic form), the initial basis (as a list of integerindexes), and a function that implements the pivoting rule. It returns the solution as a dictionary1 containing its status (did it succeed), the optimal solution, and the final basis. This function isdefined in thesimplex_generation.pyfile: you should not modify it.The functionfind_pivot_blandimplements Bland’s rule. It takes as input the tableau, andreturns the(r, s)pair giving the row and column indexes on which to pivot. This function isdefined in thesimplex.ipynbnotebook. You should not modify this function, but you will needto edit code later in this notebook.1.2.1 Task 1At the top of the file there is an integer variablestudent_id = 12345678Youmustreplace this number with your own eight digit ID. This is used to generate the problemsthe Simplex Method will solve.1.2.2 Task 2Usingfind_pivot_blandas a template, you should implementfind_pivot_largest_coefficient. This should be done within thesimplex.ipynbnote-book. A stub is given. The function should implement the largest coefficient rule givenabove.There are tests on within the notebook that perform very basic checks of the code: they do notguarantee complete correctness.1.2.3 Task 3It isessentialthat you complete task 1 before doing this step.In theSettingssection of the notebook there is a boolean variable set, asrun_timings=FalseOnce you are happy with your code, change this torun_timings=TrueWhen you run the full notebook, particularly the last cell, it will produce a spreadsheet. Thisshould take no more than one minute (on Noteable: times will vary on other machines). At theend it will have produced an Excel spreadsheettimings.xlsx.Note: if you cannot complete task 2, or want to continue on with the analysis before completingit, in theSettingssection of the notebook there is a boolean variableonly_time_Bland=FalseBy setting this toonly_time_Bland=Truea spreadsheet creating the timing data just for Bland’s rule will be produced.2
1.3 ExcelThe timing data in the Excel spreadsheet was created by looping over a range of problem sizes(quantified by the number of decision variablesn; the number of constraints was set ton+5). Foreach problem size, 50 instances were created. For each instance the simplex method was run usingboth Bland’s rule and the largest coefficient rule.The spreadsheet contains two sheets associated with the two pivoting rules. On each sheet, eachrow 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 4Download the spreadsheet from Noteable. Duplicate it and rename itanalysis.xlsx. Load theduplicateanalysis.xlsxinto Excel. Create a new sheet in the workbook; call itAnalysis. Usingappropriate Excel functions, add five columns to this sheet. The first should contain the instancesizesn. The next four should contain the average time and worst-case time for each pivoting ruleand instance size (Smallest subscript: Average,Largest coefficient: Average,Smallestsubscript: Worst,Largest coefficient: Worst). From these, create five more columns con-taining the logarithms (base 10) ofnand each time respectively.1.3.2 Task 5Create two plots. One should plot the (logarithm of the) average run time for each pivoting ruleas 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 inpdforpngformat (pdfis preferred where possible).1.3.3 Task 6Using appropriate functions (e.g.,INTERCEPT,SLOPE), compute the best fit coefficients forlog(𝑡) = 𝑝0log(𝑛)+𝑝1,where𝑡is the timing data and𝑛is the instance sizes. There should be different coefficients foreach pivoting rule and for the average and worst cases (so four pairs of coefficients in total).1.4 LaTeXOn Overleaf there is a report template. Thereport template can be found here. From the Overleafmenu (top left) you canCopy Projectto your account so you can edit your personal version. Youneed to complete the report to communicate your results.1.4.1 Task 7In the first section of the LaTeX document, include your Python code for the functionfind_pivot_largest_coefficient.1.4.2 Task 8In the second section of the LaTeX document, using big𝒪notation, analyse your Python code.3 1.4.3 Task 9In the third section of your LaTeX document, include the figures created in Excel. Add captionsexplaining what each is.Also in the third section, add a table reporting the𝑝0,1coefficients computed in task 6.1.4.4 Task 10In the fourth and final section of the LaTeX document, write one paragraph to explain which ofthe pivoting rules is more efficient in which cases. You should use the results from the complexityanalysis in task 8, and your figures and table in task 9, to back up your statements.1.5 SubmissionAll work should be submittedthrough Blackboard.The notebook should also be submitted through Noteable.Beforesubmitting through Noteable,ensure that the boolean variable is reset, sorun_timings = False.Five “things” need submitting.1.Thesimplex.ipynbnotebook.2.The (unmodified)timings.xlsxspreadsheet created bysimplex.ipynb.3.The Excel spreadsheet with the completed analysis,analysis.xlsx.4.All LaTeX and figure files needed to create the report, as azipfile. If Overleaf was used,go to theMenu(top left), and fromDownloadselectSource. This zip file should containeverything needed.5.The report as apdffile. If Overleaf was used, go the theMenu(top left), and fromDownloadselectPDF.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 4
