FOR IMMEDIATE RELEASE

Backgrounder on Feasibility and Linearity in Solver Models

A popular fiction is that advanced math skills are needed to use the Solver effectively. In fact, though, high school algebra is all that one needs to use the Solver, except in very specialized applications. The Solver does use advanced mathematical methods "under the hood," but it is based on very simple and easily understood concepts.

Solver Allocates Resources While Satisfying Constraints

Users create Solver models in Excel to find the best way to allocate scarce resources. Excel formulas are used to calculate the amounts of resources used. An example is a model which determines the best mix of products to build from an available inventory of common parts. To express the idea that resources are scarce, the Solver allows the user to define constraints.

Each constraint specifies an upper or lower limit on the value of a formula calculated by the model. For example, the constraint B10 <= C10 might specify that the sum of the parts used (calculated in cell B10) cannot exceed the inventory of parts on hand (in cell C10).

An optimal solution found by the Solver satisfies all of the constraints, and maximizes or minimizes the value of another formula, called the objective. For example, the model might seek to maximize total profits, subject to the limits on production imposed by the inventory constraints.

The Solver is allowed to change the values of certain cells, called decision variables, selected by the user. For example, these cells might specify the number of units of each product to build, and thus be used to calculate the number of parts used of each type. The Solver tries to find values for the variables that satisfy all of the constraints (such as B10 <= C10); any such set of values is called a feasible solution. The set of variable values which maximizes (or minimizes) the objective is called an optimal solution.

What Happens if the Constraints Cannot be Satisfied?

Sometimes, there is no combination of values for the decision variables that will allow the constraints to be satisfied. Such a model is said to be infeasible. The Solver automatically determines this and displays the message "Solver could not find a feasible solution." This may mean that the actual resource allocation problem which the user is trying to model has no feasible solution, but more often, it means that the user has made a mistake in defining the model and its constraints.

Since real-world applications often involve combinations of many products, regions, time periods, and so on, practical Solver models often involve hundreds, or even thousands of individual constraints. If a mistake has been made in defining one of the constraints, how can the user find this error? The Premium Solver’s new Feasibility Report can help.

The Solver initially determines that the model with all of its constraints is infeasible. When the user asks for a Feasibility Report, the Solver automatically eliminates various combinations of constraints from the problem, until it arrives at a minimal set of constraints which are conflicting – together they make the model infeasible, but if any one of them is dropped, a feasible solution could be found. This minimal set of constraints is highlighted in the Feasibility Report. The user can then focus his or her attention on the constraints where the mistake is likely to be found.

Solver Handles Linear and Nonlinear Models

The Solver can find solutions for models which include a wide variety of Excel formulas, including both linear and nonlinear formulas which depend on the decision variables. But the Solver has faster and more reliable solution methods for problems where most or all of the functions are linear – and many common problems in business, called "linear programming" problems, can be modeled this way.

• A linear function is one whose graph is a straight line. A simple example is the formula 2*A1+1 where A1 is a decision variable. (This has the form y = mx + b taught in high school algebra, where m = 2 and b = 1.) A more complex example, in three dimensions, is 1*A1+2*A2-3*A3, where A1, A2 and A3 are all decision variables.
• A nonlinear function is one whose graph is not a straight line. A simple example is the formula 1/A1 where A1 is a decision variable. (The graph of this function is a curve called a hyperbola – often covered in high school geometry.) In the formula 1/A1+2*A2, A1 occurs nonlinearly, but A2 occurs linearly; the overall formula is a nonlinear function.

A model where all of the constraints are linear functions, and the objective is a quadratic function (such as A1^2 or A1*A2) is called a "quadratic programming" problem. A popular application of this type is portfolio optimization, which determines how much money to put into each stock in a portfolio, so that the rate of return is maximized for a user-specified level of risk, or alternatively the risk is minimized for a user-specified target rate of return. The Premium Solver Plus includes a special Quadratic Solver "engine" which is faster and more accurate on this type of problem.

What Happens if the Model is Not Entirely Linear?

A model with a nonlinear objective (which is not quadratic – for example A1^3 or LOG(A1)), or where even one constraint is nonlinear, must be solved using slower, less reliable solution methods. Because speed and reliability are more important when models become larger, users are motivated to create all-linear models whenever possible. If a user tries to solve a nonlinear model with the methods for linear problems, the Solver reports that the "linearity conditions are not satisfied."

Here again, practical Solver models often involve hundreds, or even thousands of individual constraints, and hundreds or thousands of variables. If just one, or a few of the relationships in the model are nonlinear, how can the user find them? The Premium Solver’s new Linearity Report can help.

The Linearity Report lists the objective and all constraints, specifying for each one whether it is a linear or nonlinear function of the variables. It also lists the decision variables, specifying for each one whether it occurs linearly in the objective and all of the constraints, or nonlinearly in some of them. It is sometimes easier to analyze a model by starting from the decision variables, rather than the constraints.

The Linearity Report is also useful for predicting whether a nonlinear model can be solved faster using the Premium Solver Plus. The Premium Solver Plus includes an enhanced nonlinear Solver "engine" which can take advantage of any variables occurring linearly in the problem, to speed up the overall solution process. The Linearity Report provides this information about the variables.

For More Information Contact:

CompanyLongName
CompanyAddress
Tel: CompanyPhone
FAX: CompanyFAX
Internet: CompanyEmail

Copyright © 1997 CompanyLongName
Last modified: July 11, 2000