Solver - East Carolina University



Solver

Q: What is Solver?

A: Solver is an add-in to Microsoft Excel.

Q: What is an “add-in?”

A: That means it is a sort of a super-function.

Q: What do you mean by “super-function?”

A: You may be used to placing functions such as “AVERAGE” or “SUM” in a cell and telling the function which cells to average or add up. Those are fairly simple, straight-forward calculations. As mentioned in the lecture notes on “Introduction to Algorithms” we usually work with problems that require more work than a simple calculation. Solver is one way to get that work done by a computer.

Q: So, Solver is an algorithm?

A: Not exactly. Solver is an application, a specific instance of a general algorithm.

Q: Do I have to buy Solver?

A: I don’t think so. All I did was open Excel, then under “Tools” select “Add-in” and a checklist of possibilities is shown. Solver was about three-quarters the way down on my list. I clicked on the checkbox next to Solver, and then clicked OK, and I was all set up. I cannot guarantee that the version of Excel you have will allow this, but you certainly can try, and the computer lab version of Excel has Solver installed.

Q: Assuming I get Solver installed, how do I use it?

A: First, print the Excel spreadsheet I posted called “Lecture Notes Example for Solver.” I am not going to insert copies of the spreadsheet into this document, but I have set it so the row and column headings should printout as well, and will refer to the spreadsheet by cell reference.

Q: Is the information at the top of the spreadsheet (cells B2:F6) just the problem data?

A: Yes. The first step to solving any complex problem is to organize your data, and we have done that in the form of a transportation table.

Q: What is the smaller table just below that (cells B9:F13)

A: That is the solution area. Solver needs to know where to put the values for the solution. Remember that a solution to a transportation problem tells you which routes to use and how many units to ship on each route. This is where Solver will put the shipping amounts. Column B and Row 9 serve as headers – they make things easier to read, so the actual solution will be found in C10:E12.

Q: Why is there a zero in cell B9?

A: Those are your objective. For the algorithm to work, you have to tell it the total cost of any given solution. We do that in cell B9, using a function you may not know, =SUMPRODUCT.

Q: If we didn’t know this function, how would we calculate the total cost?

A: The same way I did originally, multiplying the costs in the top table (C3:E5) by the respective cells in the bottom table (C10:E12), like this: C3*C10+D3*D10+… That is tedious because you have to physically enter each of the cell references (type them or use a mouse to point-and-click while inserting the “*’ and “+” signs). It is dangerous because it is very likely you will make a mistake. A very easy mistake to make is to enter a “*” instead of a “+” and completely mess up your solution.

Q: Wouldn’t Solver catch that for you?

A: Nope. Solver allows for the possibility of non-linear functions (technically, that is what you entered), so it doesn’t mind in the least – though it really will mess up your solution.

Q: So, “=SUMPRODUCT” is a lot easier?

A: A lot. SUMPRODUCT asks you for the two ranges (C3:E5,C10:E12), and you can enter them by highlighting them with your mouse. This is a lot faster and less error prone, because you can see that you are highlighting the right cells (if you are paying attention).

Q: Do all computer programs to solve transportation problems make you do this?

A: No, just Solver. Most computer programs designed to solve transportation problems (these are called applications, or dedicated software) have pre-assigned solution areas, so as you enter the costs, the computer can automatically link the costs to the solution area. In essence, you are doing some minor computer programming and that means all the possibilities of programming errors exist for you.

Q: Great. What else do we have to do?

A: Well, dedicated software would automatically link the solution area to the supply and demand limits (constraints), but Solver can’t do that either. So you have to.

Q: How do I set up the supply limit constraints?

A: Well, a supply constraint has two parts, the left-hand side (LHS), where you add up all the shipments that the solution has made from each source (silo), and a right-hand side (RHS) where you show the maximum amount that is available to ship from each source (silo). I find it easiest to do this in two steps: first set up the LHS of the equation, where all the variables are added together, and then link that to the constraint limit (RHS).

Q: Where do I do that?

A: Around the border of the second table. In cells F10:F12, labeled “Shipped From” I have put formulae that add up the shipments for each row of the second table.

Q: What do these formulae do?

A: Since we are working with supply constraints, we are trying to make sure that the amount shipped out of each shipping point (Kansas City, Omaha, and Des Moines) is less than the amount available (the supply limits you put at the top of the page, in cells F3:F5). The computer will put the shipping amounts it decides to use in the solution area (C10:E12). We want to tell the computer that the total shipped out of Kansas City (for example) is limited. The amount shipped out of Kansas City is simply the amount shipped from Kansas City to Chicago (C10) plus the amount shipped from Kansas City to St. Louis (D10) plus the amount shipped from Kansas City to Cincinnati (E10). So in cell F10 these cells are added together. We repeat this, referring to different rows for Omaha (=SUM(C11:E11)) and Des Moines (=SUM(C12:E12)). Once you have entered the formula in cell F10, you can use the Fill-Down command if you know how to do that.

Q: Why do these formulae add up to zero?

A: We don’t have a solution yet (C10:E12 are empty), so there is no shipping plan. With no shipping plan, the total amount shipped is zero.

Q: Do we worry about programming errors when doing these formulae?

A: Constantly, but Excel can help. After you enter a formula in a cell, click on that cell and hit the “F2” key. This moves you into “Edit” mode, and Excel will use colors to match the cell references in your formula to the actual cells on the spreadsheet. This lets you see whether you clicked on the right cells when setting up your formulae, and is an excellent debugging tool.

Q: Is that all there is for the supply constraints?

A: No, you still have to link the left-hand side cells (F10:F12) to the constraint limits (F3:F5), but we will do that later.

Q: Do we have to set up any other constraints?

A: Yes, the demand constraints, cells C13:E13.

Q: Are you again setting up just the left-hand side of the equation?

A: Yes, except now we add up a column, because we are telling the computer that the amount sent to each customer (Chicago, St. Louis, and Cincinnati) must be at least what they have asked for. For Chicago, we combine Kansas City to Chicago (C10) with Omaha to Chicago (C11) and Des Moines to Chicago (C12). You repeat this for St. Louis and Cincinnati.

Q: Can I use the Fill-Down command again?

A: No, because the formulae deal with columns, so you use Fill-Right.

Q: Now what?

A: You have finished setting up the problem, so now you have to begin to tell Solver where everything is.

Q: How do we tell Solver where everything is?

A: Under Tools, you should see the word Solver – so click on it and a dialogue box will appear. It has entries for everything Solver needs to know.

Q: What is the first thing Solver needs to know?

A: The first item is “Set Target Cell.” This will currently show whatever cell you had active when you called Solver, which is probably not the cell you want. Simply click on the cell where we added together all the transportation costs (B9), and that reference will appear in the Solver dialogue box as $B$9 (the “$” are absolute references, if you don’t remember them, see an Excel manual).

Q: What is the second thing Solver needs to know?

A: You need to tell Solver whether you want the target cell (B9) to be a high number or a low number. For us, we know that if our data represents profits we want the total profit to be a high number and if the data represents costs, we want a low total. Solver doesn’t know that until we tell it, so the next line in the dialogue box says “Equal to;” and gives you three options: “Max,” “Min” and “Value of,” where “Value of” has a place to enter a target value. We are not interested in the “Value of” option, so click the white spot (it is called a radio button) next to “Min” to tell Solver to find a solution with the lowest possible cost.

Q: What is the third thing Solver needs to know?

A: The next thing to tell Solver is where to put the solution. You hopefully remember using variables in algebra, well, we are going to use certain cells as variables. That means we will let Solver change the values of those cells until it finds a set of values that obey the supply and demand limits and have as low a total cost as can be found. Up above, I referred to this as the solution area. To tell Solver where the solution area is, first click in the white box under the words “By Changing Cells” and then highlight the solution area we set aside earlier (C10:E12). The screen changes while you do this, but don’t worry about that.

Q: What is the fourth thing Solver needs to know?

A: The fourth thing is to enter the constraints. We were smart enough to arrange the formulae for the LHS of the constraints (around the second table) symmetrically with the constraint limits for the RHS of the constraints (around the first table), so all we can enter all our supply constraints at once, and all our demand constraints at once. We could rearrange the whole spreadsheet so we could enter all the constraints (supply and demand) at once, but I prefer to keep them separate.

Q: So, how do we do enter constraints?

A: In the area of the dialogue box labeled “Subject to the Constraints” click on the “Add” button. This will bring up a new dialogue box labeled “Add Constraint” with three entry areas. These three areas are just like a formula in algebra: the left-hand area (Cell Reference) takes the variables, then you set the inequality in the middle, and then you set the limit on the right (Constraint). We set up the left-hand side formulae earlier, so this is fairly easy.

Q: How do I enter the “Cell Reference?”

A: If necessary, move the dialogue box so you can see the cells where entered the “Shipped From” formulae (F10:F12). With the cursor blinking in the “Cell Reference” box, simply highlight those three cells and they should appear as F10:F12.

Q: Do I need to change the inequality?

A: You need to check to make sure it is pointed in the right direction. Since this a less-than-or-equal-to constraint (the amount shipped should be less than or equal to the supply amount), you are OK, because “=,” and highlight C6:E6 for the “Constraint” box and you are done.

Q: Are there any checks I can make to see if I have done things properly?

A: Not much. Solver doesn’t do the color-matching, so you can count the number of constraint sets to see if they are right, but outside of that you simply have to be careful. Setting up the spreadsheet so it is symmetrical helps, since you should see a pattern in the cell references, but even that can mislead you sometimes. Welcome to the world of computer programming, and start worrying.

Q: Are we ready to solve the model yet?

A: Not quite. On the right-hand side of the dialogue box is a set of buttons. Click on the “Options” button to bring up a new dialogue box. In that box are five things you may need to change: Max Time, Iterations, Precision, Tolerance, and Convergence. If Solver ever tells you it ran out of time or iterations, simply set those two to higher numbers. Always set Tolerance to 0% (this tells Solver that close isn’t good enough – you want optimal). Precision and Convergence deal with rounding errors – I prefer to set these to something incredibly precise, such as 1E-64 (that would be a decimal point followed by 63 zeroes and then a 1), but Solver, like all of Excel, suffers from rounding errors and if you do that, you will get an error message that says “Conditions for ‘Assume Linear Model (see below) Not Satisfied.” The error message makes no sense, but the only way to get rid of it is to reduce the precision and convergence values. The most I ever put is 0.0000000001 (1E-10), and sometimes I have to put even less than that.

Q: Anything else I need to worry about with the Options?

A: Yes, two more things. Below the five options we discussed above there are four check boxes. The two on the left are labeled “Assume Linear Model” and “Assume Non-Negative.” You should click both of these so a check-mark appears. “Assume Linear Model” is a way to have the computer look at the formulae you entered to see if you entered one (by mistake) as a non-linear equation (I mentioned this up above). If you did, the computer will tell you the constraints do not match a linear setup and you know to start looking for your mistake. “Assume Non-Negative” tells Solver that all solution values must be positive or zero – so you can’t ship a negative amount on a route. This may sound obvious, but nothing is obvious to a computer. If you don’t tell the computer this, it will allow some shipping amounts to be negative. Which decreases your total cost and you get a really bizarre solution. So, don’t do that. Now, click “OK” to return to the Solver dialogue box.

Q: Now are we ready to solve the model?

A: Well, you’re ready to try to solve the model. Keep in mind you may have made a mistake in entering something, but the only way to find out is to try, so click on the “Solve” button.

Q: What happens when I click “Solve?”

A: If you watch closely, the bottom-left hand corner of the screen flickers some numbers that don’t mean a whole lot, and when that stops a dialogue box labeled “Solver Results” appears. If you look at the spreadsheet, you will also notice that the solution area (C10:E12) has values for some of the routes and the total cost (B9) is also shown. If the solution matched the one in the lecture notes, you did everything properly.

Q: What do I do with the Solver Results dialogue box?

A: First, check the little message at the top. If it doesn’t say “Solver found a solution. All constraints and optimality conditions are satisfied” then you have a solution, but it is not optimal.

Q: Why would Solver give me a non-optimal solution?

A: Solver is a computer program and computers are literal. You typed in a set of data and asked for a solution, so Solver is going to give you a solution. At least Solver is nice enough to tell you when there is a problem. Not all programs will do that.

Q: Is there anything else I should do with the “Solver Results” dialogue box?

A: Right now, we don’t need it, because all the information we need is on the spreadsheet. Make sure “Keep Solver Solution” is selected, ignore the reports, and click OK. Save your spreadsheet and you are done getting your optimal solution.

Q: What are the reports that were mentioned in the Solver Results dialogue box?

A: If you ask for one of the reports, it will be inserted as a separate sheet. The “Answer” report simply shows what you have on your spreadsheet, just in a table format. “Sensitivity” provides upper and lower limits for most of your data, just like a sensitivity analysis. We don’t need that for the transportation model, but will for Linear Programming. “Limits” is a form of sensitivity analysis that isn’t all that useful, so don’t worry about it.

Q: Is that it?

A: Pretty much. We’ll do some work on altering models in the Transportation practice case, but that’s all you need to get started.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download