COMP4041 Workshop 9 Solving Nonlinear Optimization Models
Purpose: Explore the process of solving some small nonlinear optimization models with the two nonlinear solvers available in Excel: GRG Nonlinear and Evolutionary. Please note that, of course, there are better software to solve non-linear models (e.g. R, Matlab, Weka, etc.) but we keep to the tools you have used in the module. For the steps in this workshop, leave the solver options for GRG Nonlinear and Evolutionary on their default values.
Consider the following nonlinear maximization problem with one decision variable and see the corresponding spreadsheet model. The graph for this problem can be produced in Excel by plotting a series of points as shown in the spreadsheet. We can see in the graph that there is a single local optimal solution which is also the global optimum.
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒: 𝑍=−𝑋6−2𝑋4+𝑋3−3𝑋2+30𝑋 𝑆𝑢𝑏𝑗𝑒𝑐𝑡𝑡𝑜: −3≤𝑋≤3
This maximization function is concave and hence the optimization problem can be easily solved with a gradient-based optimization algorithm like GRG Nonlinear in the Excel solver. A gradient-based optimization algorithm moves iteratively in the direction of the better solution by computing the gradient of the objective function.
This model can also be solved using the Evolutionary algorithm in the Excel solver. This is a heuristic search algorithm based on stochastic mutations that seeks to explore the search space with a population of solutions. The Evolutionary algorithm normally takes longer than GRG Nonlinear to solve this small nonlinear model.
Consider the following nonlinear minimization model with one decision variable and see the corresponding spreadsheet model. Solve the model with the GRG Nonlinear algorithm and with the Evolutionary algorithm. Take note and reflect on the optimal solution reported by each algorithm.
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: 𝑍 = 𝑋6 − 136𝑋5 + 6800𝑋4 − 155000𝑋3 + 1570000𝑋2 − 5000000𝑋 𝑆𝑢𝑏𝑗𝑒𝑐𝑡𝑡𝑜: 0≤𝑋≤50
Now set the following initial value for X=15 in cell C7 and solve with GRG Nonlinear and with Evolutionary, each time starting from this initial value for X. Take note and reflect on the optimal solution reported by each algorithm.
You should now realise that there are several local optima for this nonlinear model. GRG Nonlinear will find the local optima closer to the initial value of X. Determine an initial value for X that allows GRG Nonlinear to find the global optimum for this model.
Solve the following nonlinear minimization problem using the Excel solver. Determine whether there are multiple local optima and aim to find the global optimum for this model. Compare the performance of the GRG Nonlinear and the Evolutionary algorithms in the Excel solver.
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: 𝑍 = 𝑋6 − 136𝑋5 + 6800𝑋4 − 155000𝑋3 + 1570000𝑋2 − 5000000𝑋 𝑆𝑢𝑏𝑗𝑒𝑐𝑡𝑡𝑜: 0≤𝑋≤50
Solve the following nonlinear maximization problem using the Excel solver. Aim to find the global optimum for this model. Compare the performance of the GRG Nonlinear and the Evolutionary algorithms in the Excel solver.
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒: 𝑍 = 100𝑋4 − 200𝑋2𝑋 + 100𝑋2 + 𝑋2 − 2𝑋 + 10.1𝑋4 − 20.2𝑋 + 11.1 11221122
𝑆𝑢𝑏𝑗𝑒𝑐𝑡𝑡𝑜: −2≤𝑋1,𝑋2 ≤2
Develop the optimization model in Excel and/or LP-Solve to solve the following optimization problem. You should develop a linear model, but perhaps you also want to develop a nonlinear model using ‘if’ conditionals in Excel to explore the performance of the nonlinear solvers on solving this problem.
CARS Problem
CARS are shipped from three distribution centres to five dealers using trucks. The shipping cost is based on the mileage between the source and the destination and is independent of whether the truck makes the trip with partial or full loads (a full truckload includes 18 cars). The table gives the mileage between the distribution centres and the dealers together with the supply and demand in number of cars. The transportation cost per truck mile is £25. The problem is to determine the distribution plan at the lowest overall cost.
Centre 1 Centre 2 Centre 3 Demand
Dealer 1 100 50 40 100
Dealer 2 150 70 90 200
Dealer 3 200 60 100 150
Dealer 4 140 65 150 160
35 400 80 200
130 150 140