COMP4041-LDO Workshop 1 Basics of Computational Optimization
Purpose: Familiarise with Excel Solver and LP-Solve to model and solve some small optimization problems.
Please read carefully and spend the time needed to follow the instructions in this Step because having access to the software is essential for this module.
You need access to the Excel App for all semester in this module. Please note that the online version of Excel in Microsoft 365 does not include the ‘Solver Add-in’. Therefore, you better install Office in your computer. This can be done from your University Microsoft 365 account:
More information to install and use Microsoft 265 Apps is available here:
https://www.nottingham.ac.uk/dts/knowledge-hub/microsoft-365/microsoft-365.aspx
You can also access the software in the University network by using the University computers. Alternatively, you can use the software by connecting to the University’s Windows Virtual Desktop (WVD), more information here: https://www.nottingham.ac.uk/it-services/computers/virtual.aspx
The WVD is also accessible via browser, but the performance will be worse:
https://rdweb.wvd.microsoft.com/arm/webclient/index.html
Once logged in to the WVD, the ‘Computer Science Desktop’ should appear under the group “UoN Virtual Desktop”. After you login to the “Computer Science Desktop” you can use Excel and also LP-Solve (located in the folder UoN Applications).
You need access to LP-Solve which is a free software that can be downloaded from here: http://lpsolve.sourceforge.net/5.5/ and it is also available from Moodle. Please note that the standard version of LP-Solve with the IDE is for Windows.
A version of LP-Solve for Mac computers and some brief document help is available in Moodle. However, no further technical assistance is provided in this module for LP-Solve in Mac, so it is perhaps better that you access the installation in the University network.
An optimization problem consists of 4 main components: data, decision variables, objective function and constraints. The goal is to find an optimal solution among all feasible solutions. A feasible solution is one that satisfies all the constraints. An infeasible solution is one that violates at least one constraint. Refer to (read again if needed) the BANK ABC small optimization problem described in the Lecture 1. The two equivalent algebraic models are shown below.
BANK ABC1 Algebraic Model BANK ABC2 Algebraic Model
Make sure to understand how the algebraic expressions (2)(3)(4)(5) in the BANK ABC2 model are obtained from the corresponding algebraic expressions in the BANK ABC1 model.
Download the Excel file for this workshop and examine the spreadsheet BankABC1 (not the BankABC2 spreadsheet, that one will be used later). This is the spreadsheet optimization model for the problem. Note the following in this spreadsheet model:
• The given data is arranged using a layout that seeks to intuitively reflect the optimization problem.
• The four yellow cells are the decision variables, i.e. the amount loaned for each type of loan; these are the values that we need to find.
• The green cells are calculations, some are needed to solve the problem and others are just to clarify the optimization model and solution.
• There are five constraints in the model implemented in the green cells D9, E15, E17, E19 and E21.
• The purple cell is a special calculation, the objective function, which should be maximized.
Make sure you understand the BankABC1 spreadsheet model. Enter manually some values in the yellow cells to experiment finding feasible and infeasible solutions. You can also manually enter the values for the decision variables in the optimal solution (shown in the Lecture 1).
Now you will use the Excel Solver Add-in to solve this optimization problem. Make sure the solver is activated by doing the following:
1. Click on the FILE tab and select Options
2. Click on Add-ins and then click on the Go… button next to Manage Excel Add-ins 3. Check the box for Solver Add-in and click OK
The solver add-in should now be active in the DATA tab as shown below.
While having the BankABC1 spreadsheet active, click on the Solver Add-in; the following dialog box will be shown. The objective function (maximization), decision variables and constraints are shown. Once you identify all these elements and associate them to the corresponding cells in the spreadsheet model, click on Solve and then click OK on the Solver Results dialog box. The solver should have obtained an optimal solution for the optimization problem. Note that this BANK ABC1 spreadsheet model reflects the BANK ABC1 Algebraic Model.
Excel can be used to implement an algebraic optimization model directly. Complete the spreadsheet Bank ABC2 to implement the BANK ABC2 Algebraic Model shown in Step 1 by doing this:
1. Enter the correct calculations in the green and purple cells.
2. Set the correct parameters in the Solver Add-in and solve.
1. The optimal solution obtained with both spreadsheet models Bank ABC1 and Bank ABC2 should be the same.
Now implement the same BANK ABC2 Algebraic Model in LP-Solve by doing this:
1. Open LP-Solve and enter the algebraic model as shown in the Lecture 1 notes.
2. Run the solver by selecting Action → Solve from the menu.
3. See the optimal solution found by selecting the Result tab.
4. The optimal solution obtained with LP-Solve should be the same as the one obtained with the Excel solver as shown below.
Please note that the syntax that the LP-Solve IDE accepts is very simple. Basically, it only takes fully expanded linear algebraic expressions.
Modify the Bank ABC1 spreadsheet optimization model and then solve for each problem modification below. You will need to modify the actual spreadsheet and the parameters in the Solver Add-in dialog box. Make sure to create a copy of the spreadsheet model for each problem modification because you will need them all for the online test.
a) Consider the original model but instead of maximizing, achieve an ‘Interest Income’ of exactly 30.
b) Consider the original model and solve for maximization but adding the condition that home improvement loans should be at most half of the personal overdraft loans and no less than the second mortgage loans.
c) Consider the original model and solve the problem where the objective is to minimize the windfall tax paid while achieving an ‘Interest Income’ of at least 50.
Read the following description of another small optimization problem. Identify the 4 parts of the optimization problem: data, decision variables, objective function and constraints.
Then, use the spreadsheet Apex provided to implement and solve the corresponding optimization model and find the optimal solution. Write also the corresponding algebraic optimization model and implement it in LP-Solve.
The APEX company wants to decide on the number of 27-inch and 20-inch TV sets to be produced per month at one of its factories in order to maximize the total profit. Market research indicates that at most 40 of the 27-inch TV sets and 10 of the 20-inch TV sets can be sold per month. The maximum number of work-hours available is 500 per month. A 27-inch TV set requires 20 work-hours and a 20-inch TV set requires 10 work-hours. Each 27-inch TV set sold produces a profit of £120 and each 20-inch TV set produces a profit of £80. The company has introduced a restriction in that the difference between the units produced of each TV set cannot exceed 5.