Excel 2007 Solver Could Not Find a Feasible Solution
Excel's Solver tool lets you solve optimization-modeling problems, also commonly known as linear programming programs. With an optimization-modeling problem, you want to optimize an objective function but at the same time recognize that there are constraints, or limits. While this abstract definition sounds complicated, at least at the conceptual level, optimization modeling makes common sense once you provide a concrete example.
EasyRefresher: How Optimization Modeling Works
Suppose, for example, that you're a residential real estate developer and contractor. You create and sell two products: building lots and houses. Suppose that you make $20,000 on each home you build and $15,000 on each building lot you develop and then sell. Your princi- pal financial objective is to maximize your profits, and this objective can be expressed as an objective function, or equation, that you want to maximize:
$15,000*Lots+$20,000*Houses=Profits
Of course, any objective function is limited by certain constraints. To continue with the fictional case of residential development, suppose that you have two principal limiting fac- tors: working capital and bulldozer capacity. Your working capital of $1,200,000 limits the number of lots and houses you can annually sell because every lot requires a $50,000 cash investment and every house requires a $25,000 cash investment. The fact that you have a single bulldozer available for only 3,000 hours each year also limits the number of lots and houses you can annually sell because every lot requires 80 hours of bulldozing and every house requires 200 hours of bulldozing. These two constraints can also be expressed as equations. For example, the working capital constraint can be expressed as follows:
$50,000*Lots+$25,000*Houses<=$1,200,000
This formula says the result of the formula $50,000 times the number of lots plus $25,000 times the number of houses must be less than or equal to the working capital limit of $1,200,000. The less than or equal to symbol is represented by the <= operator.
The bulldozer capacity constraint can be expressed as follows:
80*Lots+200*Houses<=3000
This formula says the result of the formula 80 times the number of lots plus 200 times the number of houses must be less than or equal to the bulldozer-hours limit of 3,000. Again, the less than or equal to symbol is represented by the <= operator.
Typically, you also have policy constraints when you work with an optimization-modeling problem. Suppose that as a matter of policy you want to maintain a certain level of activity both in developing lots and building houses. You might say, for example, that because you must maintain your team's expertise in both raw land development and residential contracting that you want to develop at least 10 lots every year and build at least 5 houses. These two constraints also need to be expressed as equations. The minimum-number-of-lots policy constraint can be expressed as follows:
Lots>=10
This formula says that you want to develop at least 10 building lots. Or, restated, this for- mula says that the lots variable must be greater than or equal to 10. The greater than or equal to symbol is represented by the >= operator.
The minimum-number-of-houses policy constraint can be expressed as follows:
Houses>=5
This formula says that you want to build at least 5 houses. Or, restated, this formula says that the houses variable must be greater than or equal to 10. Again, the greater than or equal to symbol is represented by the >= operator.
With the information provided in the preceding paragraphs of this EasyRefresherTM, I've described your fictional optimization-modeling problem. You want to maximize your profits, which can be described using the following objective function:
$15,000*Lots+$20,000*Houses=Profits
but you can't develop unlimited numbers of building lots or build unlimited numbers of houses. You are subject to the following constraints:
$50,000*Lots+$25,000*Houses<=$1,200,000
80*Lots+200*Houses<=3000
Lots>=10
Houses>=5
You can solve this equation in a variety of ways, including graphically, iteratively, or using a technique like simplex algebra. Or, you can provide the objective function and the con- straint equations to Excel and have it solve the problem, which is the solution technique described in the paragraphs that follow.
Solving an Optimization Problem
To use Excel's Solver, first build a workbook that describes your optimization-modeling problem, including its objective function and any constraints, and then tell Solver to look for an optimal solution. As long as you understand the concepts of optimization modeling, as described in the preceding EasyRefresher, this process is simple.
Setting Up Your Workbook for Solver
You take three steps to set up a workbook for solver: provide guesses of the variables that optimize your objective function, supply the objective function, and then supply the con- straint functions. Figure 6-17 shows a workbook set up to solve the example problem dis- cussed in the EasyRefresher.
To build this or any optimization model workbook, follow these steps:
- Optionally, tell Excel to display the actual formulas rather than results.
ou don't have to take this step, but because with optimization modeling you're really more interested in what the formulas look like as opposed to the results they produce, you prob- ably want to tell Excel to display formulas rather than formula results. To do this, choose the Tools menu's Options command, click the View tab, and select the Formulas check box. - Provide starting guesses for the variables.
You need to provide starting guesses for the variables you're trying to optimize. You can do this simply by entering values in cells, but I recommend you create a small schedule of variable names and variable guesses, as shown in Figure 6-17 in the worksheet range A1:B3.If you set up a worksheet range like that shown in Figure 6-17—and you really should— you'll also want to name the cells that hold your guesses. In this case, you can do this by selecting the worksheet range that holds the variable names (Lots, Houses) and guesses— A2:B3 in Figure 6-17—and then by choosing the Insert menu's Name command and then choosing the Name submenu's Create command. When Excel displays the Create Names dialog box, select the Left Column check box and click OK. - Describe the objective function.
In Figure 6-17, the worksheet describes the equation with the following formula located in cell B5:=15000*Lots+20000*HousesBecause the cells holding the variable guesses have been named Lots and Houses, the objective function uses these names in place of cell references. Note that the label in cell A5 identifies the equation, but you only need to enter the actual equation shown in cell B5. - Describe each constraint.
In Figure 6-17, the constraints are described in the worksheet range B8:C11.To describe a single constraint, you enter the constraint equation in one cell and the lim- iting constant value in another cell. For example, the working capital constraint men- tioned in the earlier EasyRefresherTM says the formula $50,000 times the number of lots plus $25,000 times the number of houses must be less than or equal to $1,200,000 (the limiting constant).To describe this first constraint, you enter the following formula in cell B8:=Lots*50000+Houses*25000and you enter the constant value which limits this formula in cell C8:1200000
To describe the second constraint—the one that quantifies the limit on bulldozer capac- ity—you enter the following formula in cell B9:
=Lots*80+Houses*200
and you enter the constant value which limits this formula in cell C9:
3000
To describe the third constraint—which comes from your minimum-number-of-lots policy constraint—you enter the following formula in cell B10:
=Lots
and you enter the constant value which limits this formula in cell C10:
10
Finally, to describe the fourth constraint—which comes from your minimum-number- of-houses policy constraint—you enter the following formula in cell B11:
=Houses
and you enter the constant value which limits this formula in cell C11:
5
Once you've completed the preceding steps, you're ready to use Solver to look for an opti- mal solution to your objective function.
Using Solver
If you set up your workbooks similar to the one shown in Figure 6-17, you will find Solver easy to use. You simply follow these steps:
- Choose the Tools menu's Solver command.
Excel displays the Solver Parameters dialog box (see Figure 6-18).
Figure 6-18. The Solver Parameters dialog box. - Identify the objective function.
Enter the address of the cell that holds your objective in the Set Target Cell box. For example, in Figure 6-17, cell B5 holds the objective function, so you would enter B5 in the Set Target Cell box. - Describe how Solver should optimize the objective function.
Use the Equal To option buttons to specify how Solver optimizes the objective function. In the case of a profit function, for example, you want to maximize the function so you click the Max button. This is the case for the workbook shown in Figure 6-17. If your objective function described costs, you would instead want to minimize the function and so would click the Min button. You may also have situations in which you want to have the objective function return a specific value, and so in this special case you would click the Value Of button and then provide the specified value. - Tell Solver which cells hold your variable guesses.
Use the By Changing Cells box to tell Excel where you've stored the variables used in the objective function and constraint equations. In Figure 6-17, for example, the work- book stores these variables in cells B2 and B3, so you could enter these two cell addresses in the By Changing Cells box. If you've named the variable cells, you can also type the cell names, as shown in Figure 6-18. Cell B2 is named Lots, and cell B3 is named Houses. - Tell Solver you want to begin describing constraints.
Click the Add button. Excel displays the Add Constraint dialog box (see Figure 6-19).
Figure 6-19. The Add Constraint dialog box. - Describe the first constraint.
To add a constraint, use the Cell Reference box to identify the cell holding the first constraint's equation, use the unnamed operator box to select an appropriate constraint operator, and then use the Constraint box to identify the cell holding the first constraint's constant value. In the case of the workbook shown in Figure 6-17, for example, you might do this by clicking the Cell Reference box and then clicking cell B8, by selecting <= operator, and then by clicking the Constraint box and then clicking cell C8. Figure 6-19 shows how the Add Constraint dialog box should look to specify this constraint. Click Add to add the constraint. Then repeat this task to add more constraints. - Add any implicit integer constraints.
In many optimization-modeling problems, you'll also have implicit integer constraints. What this means, for example, is that you can't use decimal values as part of the optimal solution. For example, you might say that you must develop an integer number of building lots or build an integer number of houses. Or restated slightly, you might say that you can't get to the end of the year and have one of your building lots only half-done or one of your houses only partially complete. To specify an integer constraint, use the Cell Reference box to identify the variable cell that must be integer and then select the int operator from the unnamed drop-down list box. Figure 6-20 shows how the Add Con- straint dialog box looks when you specify an integer constraint. Note that you don't enter the word integer in the Constraint box. Excel does that.
Figure 6-20. The Add Constraint dialog box, this time showing how an integer constraint looks. - Add any binary constraints.
In a handful of optimization modeling problems, you may also have binary constraints. A binary constraint is one in which the variable must equal either 0 or 1. To specify a binary constraint, use the Cell Reference box to identify the variable cell that must be binary and then select the bin operator from the unnamed drop-down list box. - Tell Excel you're done adding constraints.
To leave the Add Constraint dialog box after you finish describing your last constraint, click OK. Excel closes the Add Constraint dialog box and returns you to the Solver Parameters dialog box. Any constraints you've added show in the Subject To Constraints list box. - Tell Excel to look for a solution.
Click the Solve button to direct Excel to look for a solution to your optimization-mod- eling problem. Excel looks for a solution and then displays the Solver Results dialog box (see Figure 6-21).
Figure 6-21. The Solver Results dialog box. This dialog box identifies the variable values that optimize your objective function and asks what you want to do with these values.
- To tell Excel to save its solution, click the Keep Solver Solution button and click OK.
- To tell Excel to discard its solution, click the Restore Original Values button and click OK.
- To tell Excel to save its solution as a scenario, click the Save Scenario button and then provide a scenario name when prompted.
Reviewing Solver Reports
The Solver Results dialog box gives you the option of generating several reports on the optimization modeling that Solver performs. To generate these reports, click the report or reports you want when Excel displays the Solver Results dialog box (see Figure 6-21).
Understanding the Answer Report
The answer report, which Excel places on a separate worksheet, provides information about how close the optimal solution is to your original guesses and about which constraints bind, or limit, optimization. Figure 6-22 shows an example answer report. At the top of the re- port, Excel compares the original objection function formula result with the objection func- tion result provided by original variable values. In Figure 6-22, for example, Excel shows the original objective function value as 425000 and the final objective function value as 440000. The Solver in this case improves the objective function by 15000.
Beneath the comparison of the original and final values of the objective function's formula results, Excel compares the original values and final values of the variables (see Figure 6-22). This information lets you see exactly by how much Excel adjusts the variables in order to optimize your objective function.
At the bottom of the answer report, Excel analyzes the constraints by calculating the for- mula results for the constraints and then comparing these formula results to the constraint constants. This sounds like busy-work at first blush, but this information is often very use- ful in two important ways: First, you can use the Status information to see which constraints are binding, or limiting. In Figure 6-22, the binding constraint is the bulldozer hours. Second, you can use the Slack information to see how close a given constraint comes to becoming binding. In Figure 6-22, the working capital constraint shows only 25000 of slack; in other words, you have only a 2% margin of error with your working capital ($25,000 / $1,200,000).
Understanding the Sensitivity Report
The sensitivity report, which Excel also places on a separate worksheet, shows reduced gradients for the variables and the Lagrange multipliers for the constraints (see Figure 6-23). A reduced gradient value shows how the objective function would change if the vari- able value increased by 1. The Lagrange multiplier shows how the objective function would change if the constraint constant increased by 1.
A closer inspection of the sensitivity report shown in Figure 6-23, for example, shows that the reduced gradient values for both the Lots and Houses variables equal 0. This indicates that neither value can be increased. The sensitivity report does show Lagrange multipliers for the working capital constraint and for the bulldozer-hours constraint. The Lagrange multiplier for the bulldozer-hours limit, 78.125, indicates that a 1 hour increase in the number of bull- dozing hours available increases the objective function (your profits) by 78.125.
If you've created a linear optimization model—and I'll discuss linear models briefly in the next section, "Customizing Solver's Operation"—your sensitivity reports include several ad- ditional pieces of information, including reduced costs, shadow prices, objective coefficients, and constraint right-hand side ranges.
Understanding the Limits Report
The limits report, which Excel places on still another worksheet, shows you how much your variable values can change but still stay within your constraints (see Figure 6-24). For each variable, the limits report shows the calculated optimal value, the lowest possible value that is allowable, and the highest possible value that is allowable. In Figure 6-24—and this would often be the case—the lower limit and upper limit values equal the optimal values. This shows that these variable values can be changed without affecting the optimal solution or violat- ing constraints. Note, however, that some optimization problems do allow you to change variable values while continuing to optimize the function and continuing to stay within the stated constraints. This happens when there are multiple sets of variable values that opti- mize the equation.
Customizing Solver's Operation
The Solver Parameters dialog box provides an Options button that you can click to display the Solver Options dialog box (see Figure 6-25). The Solver Options dialog box lets you customize the way in which Solver works out your problem. The paragraphs that follow briefly describe each of the Solver options along with how and why you might change their settings.
Max Time and Iterations
A handful of these options are essentially self-descriptive. The Max Time box, for example, lets you specify how long Solver should work on a problem, and can it be set as high as 32,767 seconds (which is over nine hours). The Iterations box lets you specify how many iterations Solver should work on a problem, and it can be set as high as 32,767.
Precision
The Precision box lets you specify how precise Solver should be in checking a possible optimal solution against your constraints. A precision setting of 0.000001, the default set- ting, tells Excel that if a constraint formula value is within 0.000001 of the constraint con- stant, it meets the constraint. You can set the Precision box to any value from 0 to 1. To loosen your precision, use a larger Precision value. To tighten your precision, use a smaller Preci- sion value. As you boost your precision, predictably, Excel takes longer to reach a solution.
Tolerance
The Tolerance box lets you specify how precise Solver should be in making sure that any integer constraints are met. The default Tolerance setting of 5, or 5%, means that if an objective function variable is within 5% of an integer value—from 95% to 105%, in other words—Excel can consider it to be an integer. The Tolerance setting, by the way, applies only to optimization problems that use integer constraints. As you increase your precision, predictably, Excel takes longer to reach a solution.
Convergence
The Convergence box lets you indicate when Excel should stop looking for a better solu- tion. You can set the Convergence value to any fractional value between 0 and 1. When the change in the objective function is less than the value shown in the Convergence box, Ex- cel stops looking for a better solution. The Convergence setting, by the way, applies only to nonlinear optimization-modeling problems. As you reduce the convergence setting (i.e., increase the precision), predictably, Excel takes longer to reach a solution.
Assume Linear Model
If the relationships in your optimization are linear, you can select the Assume Linear Model check box. By doing this, you simplify the calculations that Excel has to make and, thereby, speed things up.
Assume Non-Negative
If you want to tell Excel that your variables must be equal to or greater than 0 when you haven't set a lower limit constraint, you can select the Assume Non-Negative check box. In effect, when you check this box, you tell Excel to create another, implicit set of constraints.
Use Automatic Scaling
You should select the Automatic Scaling check box when you're working with variables and formula results that differ in magnitude. An example of this situation is when you're solv- ing for a rate of return (a percentage) using a set of large dollar variables.
Show Iteration Results
You can select the Show Iteration Results check box to direct Excel to pause after each calculation iteration. After each calculation iteration, Excel displays a Show Trial Solution dialog box. You can save the trial solution by clicking the Save Scenario button. Or you can continue to work toward the solution by clicking the Continue button. To terminate the iterations, click the Stop button.
Estimates
You use the Estimates option buttons—Tangent and Quadratic—to choose the approach that you want Excel to use to come up with the first trial solution. Select Tangent if you want Excel to extrapolate linearly from a tangent vector. Select Quadratic if you want Excel to extrapolate quadraticly—a technique which may yield better results for nonlinear optimization-modeling problems.
Derivatives
You use the Derivatives option buttons—Forward and Central—to specify the differencing used to estimate partial derivatives of the objective function and constraint function for- mulas. Typically, you can click the Forward button. However, if an optimization problem can't be solved with Forward derivatives, you can click the Central button. Using differen- tials near the center of a target often takes more calculations to solve, but can be better with highly constrained problems such as airline ticket prices.
Search
The Search option buttons—Newton and Conjugate—let you choose the algorithm Excel uses to find an optimal solution. If your personal computer has lots of free memory, click the Newton button to reduce the number of calculation iterations (albeit at the expense of using more memory). If your personal computer doesn't have extra memory, click the Con- jugate button to allow more time so that your computer does't use as much memory.
Save Model and Load Model
The Save Model and Load Model buttons let you save an optimization model description. To save a model—such as the equations that you set up for the scenario with houses, lots, working capital and bulldozers, click the Save Model button and then specify the empty worksheet range that Excel should use to save the model. To load a model, click the Load Model button and then specify the worksheet range holding the model.
Understanding Solver Error Messages
For most simple optimization problems, Excel rather quickly finds a solution to your problem and displays the Solver Results dialog box. In more complicated problems—unfortunately, those you're likely to encounter in real life—Excel may encounter difficulties. In these cases, it may display one of the error messages described in the following paragraphs.
Solver has converged to the current solution
This message means that while Excel has found what it appears to be a solution, there may be a better solution. To direct Excel to look for a better solution, reduce the Convergence setting using the Solver Options dialog box, as described in the preceding section, "Cus- tomizing Solver's Operations."
Solver cannot improve the current solution
This message indicates that Excel has calculated a rough, appropriate solution, but there may be a better solution. To direct Excel to look for a better solution, adjust the Precision setting to a larger value using the Solver Options dialog box. Again, the preceding section explains how to do this.
Stop chosen when the maximum time limit was reached
This message indicates that Excel ran out of time. You can attempt to retry solving the solutionusingalargerMaxTimesetting.TospecifyalargerMaxTimevalue,usetheSolver Options dialog box.
Stop chosen when the maximum iteration limit was reached
ThismessageindicatesthatExcelranoutofiterations.Youcanattempttoretrysolvingthe solution using a larger Iterations setting. To specify a larger Iterations value, use the Solver Options dialog box.
The Set Target Cell values do not converge
This message indicates that the objective function continues to increase or decrease even though all the constraints are already satisfied. In other words, with each iteration, Excel gets a better objective function value, but doesn't appear any closer to a final objective function value. If you encounter this error, review your objective function and constraints to make sure that you've correctly described the optimization-modeling problem.
Solver could not find a feasible solution
This message probably indicates that your optimization-modeling problem has no answer. Alternatively, this error message may suggest that you've incorrectly described the objec- tive function or, perhaps more likely, one or more of the constraints. In the previous model, if your working capital was limited to $600,000, you would not have enough cash to work the minimum required number of lots and houses. There would be no feasible solution.
Conditions for Assume Linear Model are not satisfied
This message indicates you selected the Assume linear model check box, which appears on the Solver Options dialog box, but Excel, after reviewing the calculation results, concludes your model isn't linear. If you see this message, first display the Solver Options dialog box and select the Use Automatic Scaling check box. Then attempt to solve your optimization model again. If you get the message error a second time, display the Solver Options box again, but this time clear the Assume Linear Model check box. Then attempt to solve your problem again.
Solver encountered an error value in a target or constraint cell
This message indicates that one of your formulas results in an error value or that you've incorrectly specified an integer or binary constraint. To address this Solver problem, you need to fix the incorrect formula.
There is not enough memory available to solve the problem
This message, as you would suspect, indicates that Excel doesn't have enough memory to successfully run Solver. To free up memory, try closing open documents and any other open programs. You may also want to add memory to your personal computer.
Excel 2007 Solver Could Not Find a Feasible Solution
Source: https://stephenlnelson.com/articles/optimization-modeling-solver-excel/