Review: Elements of an Optimization Model

The basic purpose of the Solver is to find a solution – that is, values for the decision variables in your model – that maxi­mizes or mini­mizes the objective function while satisfying all of the model’s constraints.  This is exactly what we used Solver for in the Product Mix Example – to find the values of the decision variables (production quantities) that maximize the objective function (profits) subject to the constraints (materials available).  In short, optimization helps you determine the best decisions to make given the specific constraints of your business context. Before moving on to the next module, let’s review this optimization framework in more detail.

Some of the input values in your model may be numbers that you use, but that you cannot change on your own – for example, each product’s unit profits or materials requirements in the Product Mix Example.  We’ll call these values the parameters of the model. We’ll assume for now that you have only one set of parameter values to consider, but later in the course we’ll cover Parametric Optimization, which allows you to analyze several cases, scenarios, or variations of the same problem to solve, with the parameter values changing in each problem variation. In addition, we’ll assume for now that parameter values are certain, but later in the course we’ll cover Stochastic Optimization, in which the parameter values can be uncertain.

On the other hand, some of the input values in your model may be quantities that you can change – that is, they are under your control in the course of finding a solution.  We’ll refer to these as the decision variables (also sometimes referred to as simply “variables” or “changing cells”).  The Solver will find optimal values for these decision variables.

The quantity you want to maximize or minimize is called the objective function.  For example, this could be a calculated value for projected profits (to be maximized), or costs, risk, or error values (to be minimized).

You may have a Solver model that has nothing to maximize or minimize, in which case no cell will be listed for the objective.  In this situation the Solver will simply find a solution that satisfies the constraints.  Typically this will be only one of many such solutions, located close to the starting values of the decision variables.

In the Excel Solver, constraints are specified by giving a cell reference such as A1 or A1:A5 (the “left hand side”), a relation (<=, = or >=), and an expression for the “right hand side.”  A constraint such as A1:A5 <= 10 is shorthand for A1 <= 10, A2 <= 10, A3 <= 10, A4 <= 10, A5 <=10.  A constraint such as A1:A5 <= B1:B5 is shorthand for A1 <= B1, A2 <= B2, A3 <= B3, A4 <= B4, A5 <= B5.

A constraint is satisfied if the condition it specifies is true within a small tolerance.  This is a little different from a logical formula such as =A1>=0 evaluating to TRUE or FALSE which you might enter in a cell.  In this example, if A1 were -0.0000001, the logical formula would evaluate to FALSE, but with the default ASP Precision setting (found under the Engine tab), the constraint would be satisfied.  This is necessary because of the numerical methods used to find solutions to optimization models and the finite precision of computer arithmetic.

Examples of Optimization Applications

Here are some examples of optimization problems in various industries:

Finance and Investment

Working capital management involves deciding how much cash to allocate to different purposes (accounts receivable, inventory, etc.) across multiple time periods, to maximize interest earnings.

Capital budgeting involves deciding how much money to invest in projects that initially consume cash but later generate cash, to maximize a firm's return on capital.

Portfolio optimization -- creating "efficient portfolios" -- involves deciding how much money to invest in stocks or bonds to maximize return for a given level of risk, or to minimize risk for a target rate of return.

Manufacturing

Job shop scheduling involves deciding how to assign work orders to different types of production equipment, to minimize delivery time or maximize equipment utilization.

Blending (of petroleum products, ores, animal feed, etc.) involves deciding how to combine raw materials of different types and grades, to meet demand while minimizing costs.

Cutting stock (for lumber, paper, etc.) involves deciding how to cut large sheets or timbers into smaller pieces, to meet demand while minimizing waste.

Distribution and Networks

Routing (of goods, natural gas, electricity, digital data, etc.) involves deciding which paths items should move through to arrive at various destinations, to minimize costs or maximize throughput.

Loading (of trucks, rail cars, etc.) involves deciding how items of different sizes should be placed in vehicles so as to minimize wasted or unused space.

Scheduling of everything from workers to vehicles and meeting rooms involves deciding how resources should be allocate to various tasks in order to meet demand while minimizing overall costs.

A Note on Model Scaling

As you begin to develop more complex optimization models, it is very important to avoid creating a poorly scaled model.  A poorly scaled model is one that computes values of the objective, constraints, or intermediate results that differ by several orders of magnitude.  A classic example is a financial model that computes investment amounts in millions or billions of dollars, while also computing return or risk measures in fractions of a percent.  Because of the finite precision of computer arithmetic, when these values of very different magnitudes (or others derived from them) are added, subtracted, or compared – in the user’s model or in the Solver’s own calculations – the result will be accurate to only a few significant digits.  After many such steps, the Solver may suffer from “numerical instability.”  This can cause Solver to return messages such as “Solver could not find a feasible solution,” “Solver could not improve the current solution,” or even “The linearity conditions required by this Solver engine are not satisfied,” along with results that are suboptimal or otherwise very different from your expectations.

Scaling issues can be partially mitigated using ASP’s “Use Automatic Scaling” option on the Task Pane’s Engine tab.  When this option is set to True, the Solver will rescale the values of the objective and constraint functions internally in order to minimize the effects of poor scaling.  However, this can only help with the Solver’s own calculations – it can’t help with poorly scaled results that arise in the middle of your Excel formulas.

The best way to avoid scaling problems is to carefully choose the units used in your model so that all computed results are within a few orders of magnitude of each other.  For example, if you express investment dollar amounts in units of millions, then the actual numbers computed on your worksheet may range from perhaps 1 to 1,000.  When combined with return rates of a fraction of a percent, this model has much better scaling than a model that uses the actual dollar units.

If you’re experiencing unusual optimization results that you suspect may be due to poor scaling, you can check your model for scaling problems that arise in the middle of your Excel formulas by selecting ASP’s “Scaling Report” after solving your model.  This report appears as a choice under Reports – Optimization whenever you get a result that may be due to a poorly scaled model, such as “Solver could not find a feasible solution,” “Solver could not improve the current solution,” or “The linearity conditions required by this Solver engine are not satisfied.”  If you are puzzled by a result, and you see that the Scaling Report is available, we highly recommend that you select it, click OK, and then examine the report contents.

For more details on model scaling and ASP’s Scaling Report, please refer to the ASP Reference Guide.