Introduction to

Management Science

Issue 8. Non-linear

Introduction to

Table of Contents
Chapter 10 (Nonlinear Programming)

The Challenges of Nonlinear Programming

NLP with Decreasing Marginal Returns:
Wyndor
NLP with Decreasing Marginal Returns:
Portfolio Selection
Separable Programming
Difficult Nonlinear Programming Problems
Evolutionary Solver and Genetic Algorithms
Nonlinear and Separable Programming
Evolutionary Solver
Issue 8. Non-linear

Introduction to

Recall - Optimization problems

In an optimization problem, we seek to
minimize or maximize a specific quantity
(the objective), which depends on a finite
number of input variables.
These variables may be independent of one another, or
They may be related through one or more constraints.

Example:
minimize:

z = x12 + x22

subject to:

x1 x2 = 3
x2 3

Issue 8. Non-linear

Introduction to

A mathematical program
A mathematical program is an optimization
problem in which the objective and
constraints are given as mathematical
functions and functional relationships.
optimize:

z = f(x1, x2, x3, , xn)

subject to: g1(x1, x2, x3, , xn)

g2(x1, x2, x3, , xn)
g3(x1, x2, x3, , xn)
.
gm(x1, x2, x3, , xn)

Issue 8. Non-linear

Introduction to

b1
b2
b3

bm

Linear programs
A mathematical program is linear if f(x1, x2, x3,
, xn) and each gi(x1, x2, x3, , xn), i = (1, 2, ,
m) are linear in each of their arguments:

f(x1, x2, , xn) = c1x1 + c2x2 + + cnxn

and
gi(x1, x2, , xn) = ai1x1 + ai2x2 + + ainxn
Where cj and aij (i = 1, 2, , m; j = 1, 2,
, n) are known constants.
Any other mathematical program is nonlinear.
Issue 8. Non-linear
Introduction to

Integer programs
An integer program is a linear program
with the additional restriction that the
input variables be integers.
It is not necessary that the coefficients in
the arguments f(x) and gi(x) and the
constants bi also be integers, but they
frequently may be.

Issue 8. Non-linear

Introduction to

Quadratic (non-linear) programs

A quadratic program is an example of a nonlinear program in which each constraint is
linear, but the objective function has the
form:

f(x1, x2, , xn) = injncijx1xj + indixi

Where cij and di are known constants.
Example:
minimize: z = x12 + x22 Quadratic program

with linear
subject to: x1 x2 = 3
constraints, quadratic
x2 3
objective function, n
=
2
variables,
c
=
1,
11
Issue 8. Non-linear
Introduction to

Examples of Linear and Nonlinear

Formulas
Linear Formulas

Nonlinear Formulas

SUMPRODUCT(D4:D6, C4:C6)
[(D1 + D2) / D3] * C4
IF(D2 >= 2, 2*C3, 3*C4)
SUMIF(D1:D6, 4, C1:C6)
SUM(D4:D6)
2*C1 + 3*C4 + C6
C1 + C2 + C3

SUMPRODUCT(C4:C6,
C1:C3)
[(C1 + C2) / C3] * D4
IF(C2 >= 2, 2*C3, 3*C4)
SUMIF(C1:C6, 4, D1:D6)
ROUND(C1)
MAX(C1, 0)
MIN(C1, C2)
ABS(C1)
SQRT(C1)
C1 * C2
C1 / C2
C1 ^2

Data cells are located in D1:D6 and changing cells are in C1:C6.
Issue 8. Non-linear

Introduction to

The Challenges of Nonlinear

Programming
Nonlinear programming is used to model
nonproportional relationships between
activity levels and the overall measure of
performance, whereas linear programming
assumes a proportional relationship.
Constructing the nonlinear formula(s) needed
for a nonlinear programming model is
considerably more difficult than developing
the linear formulas used in linear
programming.
Solving a nonlinear programming model is
often much more difficult (if it is possible at
all) than solving a linear programming model.
Issue 8. Non-linear

Introduction to

The Challenge of Nonproportional

Relationships
Proportionality Assumption of Linear
Programming:
The contribution of each activity to the value of the
objective function is proportional to the level of the activity.
In other words, the term in the objective function involving
this activity consists of a coefficient times the decision
variable.

Nonlinear programming problems arise when

any activity has a nonproportional
relationshipwhere the contribution of the
activity to the measure of performance is not
proportional to the level of the activity.
Issue 8. Non-linear

Introduction to

Profit Graphs for Wyndor Glass Co.

(Proportional Relationship)

Weekly
Profit
($)

Weekly
Profit
($)

1200

3000

2500
900
2000
600

1500
1000

300
500

2
Productionratefordoors

Issue 8. Non-linear

Introduction to

2
4
Productionrateforwindows

Profit Graphs with Nonproportional

Relationships
Decreasing Marginal Returns

Issue 8. Non-linear

Introduction to

Piecewise Linear with

Decreasing Marginal Returns

Profit Graphs with Nonproportional

Relationships
Decreasing Marginal Returns
Except for Discontinuities

Issue 8. Non-linear

Introduction to

Increasing Marginal Returns

Constructing a Nonlinear Formula

A
1
2
3
4
5
6
7
8

Constructing a Nonlinear Formula

Level of Activity
2
4
5
7
10

Profit
$16
$24
$28
$30
$33
Profit vs. Level of Activity

Profit

$35
$30
$25
$20
$15
$10
$5
$0
0

Level of Activity (x)

Issue 8. Non-linear

Introduction to

10

Add Trendline Dialogue Box

Issue 8. Non-linear

Introduction to

Add Trendline Options

Issue 8. Non-linear

Introduction to

The Trendline (Quadratic Equation)

Issue 8. Non-linear

Introduction to

Solving Nonlinear Programming

Models
Consider the following model in algebraic
form:
maximize:
Profit = 0.5x5 6x4 + 24.5x3 39x2 + 20x
subject to:
x5
x0

Issue 8. Non-linear

Introduction to

Solver Solution Starting with x = 0

A
1

<=

Maximum
5

A Simple NLP

2
3
4
5
6
7

Issue 8. Non-linear

x=

0.371

Profit = 0.5x5-6x4+24.5x3-39x2+20x
=
$3.19

Introduction to

Solver Solution Starting with x = 3

A
1

<=

Maximum
5

A Simple NLP

2
3
4
5
6
7

Issue 8. Non-linear

x=

3.126

Profit = 0.5x5-6x4+24.5x3-39x2+20x
=
$6.13

Introduction to

Solver Solution Starting with x = 4.7

A
1

<=

Maximum
5

A Simple NLP

2
3
4
5
6
7

Issue 8. Non-linear

x=

5.000

Profit = 0.5x5-6x4+24.5x3-39x2+20x
=
$0.00

Introduction to

The Profit Graph

Profit($)

Issue 8. Non-linear

Introduction to

Original Wyndor Glass Co.

Spreadsheet
A
1
2
3
4
5
6
7
8
9
10
11
12

<=
<=
<=

Hours
Available
4
12
18

Wyndor Glass Co. Product-Mix Problem

Unit Profit

Plant 1
Plant 2
Plant 3

Units Produced

Issue 8. Non-linear

Doors
$300

Windows
$500

Hours Used Per Unit Produced

1
0
0
2
3
2
Doors
2

Windows
6

Introduction to

Hours
Used
2
12
18

Total Profit
$3,600

Wyndor Glass with Marketing Costs

Market research indicates that Wyndor could sell small numbers
of doors and windows with no advertising. However, extensive
advertising would be required to sell all that could be produced.
A curve-fitting procedure was used to estimate the weekly
marketing costs required to sustain a production rate of D doors
and W windows:
Marketing cost for doors = $25D2
Marketing costs for windows = ($66 2/3)W2

The gross profit per door sold is about $375, and the gross
profit per window is about $700. Therefore, the net profits are
as follows:
Net profit for doors = $375D $25D2
Net profit for windows = $700W ($662/3)W2

Thus, the revised objective function is

maximize: Profit = $375D 25D2 + $700W ($662/3)W2
Question: Considering the nonlinear marketing costs, how many
doors and windows should Wyndor produce?
Issue 8. Non-linear

Introduction to

Profit Graphs for Doors and Windows

Weekly
profit
($)
1,800

Weekly
profit
($)

1,600

1,200

1,200

1,000

1,000

800

800

600

600

400

400

200

200
0

1,400

D
2
4
0
2
4
6
ProductionratefordoorsProductionrateforwindows

Issue 8. Non-linear

Introduction to

Spreadsheet Formulation

Issue 8. Non-linear

Introduction to

Graphical Display of Nonlinear

Formulation
W

Productionrateforwindows 6

5
3
5
(3,4)=optimalsolution
14
28
4
Profit=$2,800
3

Feasible
region

Profit=$2,708
Profit=$2,600
Profit=$2,500

Issue 8. Non-linear

2
3
Productionratefordoors

Introduction to

Portfolio Selection
It is now common practice for professional managers
of large stock portfolios to use computer models
based on nonlinear programming to guide them.
Investors are concerned about both the expected
return and the risk.
One way of formulating their approach is as a
nonlinear version of a cost-benefit trade-off problem:
Minimize: Risk
subject to: Expected return Minimum acceptable level

Consider a portfolio with 3 stocks.

Question: What is the portfolio that will minimize the
risk subject to achieving at least an 18% expected
return?
Issue 8. Non-linear

Introduction to

Data for Stocks

Stock
1

Risk
(Standa
Joint Risk
Expect
rd
Pair
per Stock
ed
Deviati
of
(Covarianc
Return
on)
Stocks
e)
21%
25%
1 and 2
0.040

30

45

1 and 3

0.005

2 and 3

0.010

Issue 8. Non-linear

Introduction to

Algebraic Formulation
minimize:
Risk = (0.25S1)2+(0.45S2)2+(0.05S3)2+2(0.04)S1S2+2(0.005)S1S3+2(0.01)S2S3
subject to:
(21%)S1 + (30%)S2 + (8%)S3 18%
S1 + S2 + S3 = 100%
and
S1 0, S2 0, S3 0.

Issue 8. Non-linear

Introduction to

Portfolio selection spreadsheet model

Issue 8. Non-linear

Introduction to

Using Solver Table to examine tradeoffs

between expected return and risk

Issue 8. Non-linear

Introduction to

Wyndor Glass when overtime is

needed

Wyndor Glass has accepted a special order for hand-crafted

goods to be made in plants 1 and 2 throughout the next four
months.
Filling this order will require borrowing certain employees from
the work crews of regular products.
The remaining workers will need to work overtime to utilize the
full production capacity of each plants machinery for the
regular products.
The original constraints of Hours Used Hours Available are
still valid. However, the objective function will need to be
modified because of the additional cost of using overtime work.
In particular, because of the additional cost, the profit per unit
will be reduced for those units that require overtime.
Question: Considering overtime costs, how many doors and
windows should Wyndor produce?
Issue 8. Non-linear

Introduction to

Data for Wyndor When Overtime is

Needed
Maximum Weekly
Production
Produc
t

Regula
r
Time

Overti
me

Doors

Window
s

Total

Regula
r
Time

Overti
me

$300

$200

500

100

(and 3D + 2W 18)

Issue 8. Non-linear

Profit per Unit

Produced

Introduction to

Profit Graphs for Doors and Windows

Weekly
profit
($)
1,800
1,500

Weekly
profit
($)
1,100
900

3
4
Productionratefordoors

Issue 8. Non-linear

Introduction to

3
Productionrateforwindows

The Separable Programming

Technique

For each activity that violates the proportionality

assumption, separate its profit graph into parts, with a
line segment in each part.
Then, instead of using a single decision variable to
represent the level of each such activity, introduce a
separate new decision variable for each line segment on
that activitys profit graph.
Since the proportionality assumption holds for these new
decision variables, formulate a linear programming model
in terms of these variables.
For the Wyndor problem, these new decision variables are
DR = Number of doors produced per week on regular time
DO = Number of doors produced per week on overtime
WR = Number of windows produced per week on regular time
WO = Number of windows produced per week on overtime
Issue 8. Non-linear

Introduction to

Separable programming spreadsheet

model

Issue 8. Non-linear

Introduction to

Separable Programming with smooth

profit graphs

Profit

Profitgraph
Approximation

Levelofactivity
Issue 8. Non-linear

Introduction to

Advantages of Separable
Programming

The Excel Solver can readily solve nonlinear

problems that have decreasing marginal returns,
with the advantage that no approximation is
needed.
However, the separable programming approach also
has certain advantages:
Converting the problem into a linear programming problem tends to
make it quicker to solve, which can be very helpful for large
problems.
A linear programming formulation makes available Solvers
Sensitivity Report.
Separable programming only requires estimating the profit from
each activity at a few points. Therefore, it is not necessary to use a
curve fitting method to estimate the formula for the profit graph.
Issue 8. Non-linear

Introduction to

Wyndor Problem with Both Overtime

Costs and
Nonlinear Marketing Costs

The previous spreadsheet model does not

include nonlinear marketing costs.

Recall that the curve-fitting procedure was used

to estimate the weekly marketing costs required
to sustain a production rate of D doors and W
windows:
Marketing cost for doors = $25D2
Marketing costs for windows = ($662/3)W2

Question: Considering both overtime costs and

nonlinear marketing costs, how many doors and
windows should Wyndor produce?
Issue 8. Non-linear

Introduction to

Data for Wyndor with Overtime

Costs and
Nonlinear Marketing Costs
Maximum Weekly
Production

Regula
r
Time

Overti
me

Doors

Window
s

Produc
t

Issue 8. Non-linear

Gross Unit
Profit

Total

Regula
r
Time

Overti
me

Marketin
g
Costs

$375

$275

$25D2

700

300

662/3W2

Introduction to

Weekly Profit from Producing Doors

Gross
Profit

Marketin
g
Costs

Profit

Incremen
tal
Profit

$0

$0

$0

375

25

350

350

750

100

650

300

1,125

225

900

250

1,400

400

1,000

100

Issue 8. Non-linear

Introduction to

Weekly Profit from Producing

Windows

Gross
Profit

Marketin
g
Costs

Profit

Increme
ntal
Profit

$0

$0

$0

700

662/3

6331/3

6331/3

1,400

2662/3

1,1331/3

500

2,100

600

1,500

3662/3

2,400

1,0662/3

1,3331/3

1662/3

2,700

1,6662/3

1,0331/3

300

3,000

2,400

600

4331/3

Issue 8. Non-linear

Introduction to

Separable Programming
Spreadsheet Model

Issue 8. Non-linear

Introduction to

Nonlinear Programming Spreadsheet

Model

Issue 8. Non-linear

Introduction to

Difficult Nonlinear Programming

Problems

Even if a model has a nonlinear objective function, so long as

the model has certain properties (e.g., linear constraints,
decreasing marginal returns), the Solver can easily find an
optimal solution.
In some cases separable programming can be used to model a
nonlinear problem in such a way that linear programming can
be used.
However, if a problem has increasing marginal returns, or
nonlinear functions in the constraints, or disconnected profit
graphs, finding a solution is often much more difficult.
Such problems may have many local optima
Solver can get stuck at local optima, rather than finding the global optimum

One approach with such problems is to solve the problem many

times, each time starting with a different initial solution.
Solver Table can be used to do this process more systematically when
there are only one or two variables.
Issue 8. Non-linear

Introduction to

Using Solver Table to try different

starting points
A
1
2
3
4
5
6
7
8
9
10
11
12

Using Solver Table to Try Different Starting Points

x=

0.371
5

<=
3

Maximum
5

Starting
Point
x

Solution
x *

0
1
2
3
4
5

0.371
0.371
0.371
3.126
3.126
3.126
5.000

Profit = 0.5x -6x +24.5x -39x +20x

=

$3.19

Issue 8. Non-linear

Introduction to

Profit
$3.19
$3.19
$3.19
$6.13
$6.13
$6.13
$0.00

Evolutionary Solver and Genetic

Algorithms

Evolutionary Solver uses an entirely different approach

than the standard Solver to search for an optimal solution
for a model.
The philosophy of Evolutionary Solver is based on
genetics, evolution and the survival of the fittest. Hence,
this type of algorithm is sometimes called a genetic
algorithm.
The standard Solver starts with a single solution, and
then moves in directions that will improve this solution.
Evolutionary Solver begins by randomly generating a
whole population of solutions.
After generating the population, Evolutionary Solver
creates a new generation by pairing off solutions in the
population to create offspring, combining some
elements from each parent.
Issue 8. Non-linear

Introduction to

Evolutionary Solver and Genetic

Algorithms
Among solutions in the population, some will be good
(or fit) and some will be bad (or unfit), as
measured by evaluating the objective function.
Borrowing from the principles of evolution and survival
of the fittest, the fit members are allowed to
reproduce more frequently than the unfit members.
Another key feature is mutation. Like gene mutation
in biology, Evolutionary Solver will occasionally make
a random change in a member of the population. This
helps the algorithm get unstuck if it is getting trapped
near a local optimum.
Evolutionary Solver keeps creating new generations of
solutions until there have been no improvements for
several consecutive generations.
Issue 8. Non-linear

Introduction to

Selecting a portfolio to beat the

market
A common goal of portfolio managers is to beat the market.
If we assume that past performance is somewhat of an
indicator of the future, then picking a portfolio that beat the
market most often in the past might yield a portfolio that
will more than likely beat the market in the future.
Consider a portfolio of five large stocks traded on the New
York Stock Exchange (NYSE):

America Online (AOL)

Boeing (BA)
Ford (F)
Procter & Gamble (PG)
McDonalds (MCD)

Question: What mix of these five stocks will yield a portfolio

that is likely to beat the market in the future?
Issue 8. Non-linear

Introduction to

Spreadsheet Model
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Return
2.38%
-18.12%
4.95%
-4.08%
-1.83%
13.91%
-5.73%
-17.82%
11.90%
-1.53%
-3.01%
23.11%
51.00%
-14.51%
10.67%
24.46%
6.66%
10.66%
16.99%
5.69%
3.15%
-0.99%
-4.56%
17.48%

Beat
Market?
No
No
Yes
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes

Market
(NYSE)
8.45%
-12.53%
4.38%
-9.32%
-0.93%
3.31%
-0.91%
-0.40%
9.70%
-8.54%
7.38%
1.31%
18.11%
-12.83%
1.04%
12.05%
2.81%
7.42%
16.14%
1.59%
6.80%
2.26%
3.54%
5.28%

Sum
100%

100%

Beating the Market (Evolutionary Solver)

Quarter
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1

Year
2001
2001
2001
2001
2000
2000
2000
2000
1999
1999
1999
1999
1998
1998
1998
1998
1997
1997
1997
1997
1996
1996
1996
1996

Portfolio

Issue 8. Non-linear

AOL
-3.02%
-37.55%
32.00%
15.37%
-35.14%
1.46%
-21.37%
-11.36%
45.82%
-5.40%
-25.17%
89.52%
177.96%
6.18%
53.89%
50.96%
19.96%
35.61%
30.90%
27.82%
-6.34%
-18.86%
-21.87%
49.33%

BA
16.35%
-39.56%
0.07%
-15.34%
2.55%
54.71%
10.98%
-8.44%
-2.48%
-2.83%
29.83%
4.21%
-4.92%
-23.00%
-14.51%
6.51%
-10.10%
2.59%
7.60%
-7.39%
12.70%
8.46%
0.58%
10.53%

F
-8.54%
-28.49%
-11.80%
21.28%
-7.00%
3.66%
-6.39%
-13.83%
6.10%
-10.96%
-0.44%
-3.41%
24.87%
-20.34%
-8.94%
33.46%
7.62%
18.75%
21.12%
-2.71%
3.20%
-3.47%
-5.82%
19.05%

PG
8.77%
14.71%
2.54%
-19.80%
17.07%
18.06%
0.00%
-48.20%
16.87%
6.38%
-10.02%
7.26%
28.38%
-21.89%
7.93%
5.72%
15.57%
-2.21%
23.09%
6.62%
10.39%
7.59%
6.93%
2.11%

MCD
-1.64%
0.30%
1.92%
-21.91%
13.37%
-8.35%
-11.87%
-7.29%
-6.79%
5.17%
-9.24%
17.98%
28.69%
-13.50%
15.00%
25.65%
0.26%
-1.42%
2.25%
4.13%
-4.22%
1.34%
-2.60%
6.37%

0%
<=
20.0%
<=
100%

0%
<=
20.0%
<=
100%

0%
<=
20.0%
<=
100%

0%
<=
20.0%
<=
100%

0%
<=
20.0%
<=
100%

Number of Quarters
Beating the Market
14

Introduction to

Premium Solver Dialogue Box

Issue 8. Non-linear

Introduction to

Solver Options Dialogue Box

Issue 8. Non-linear

Introduction to

Limit Options Dialogue Box

Issue 8. Non-linear

Introduction to

Evolutionary Solver Spreadsheet

Solution
A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Return
10.20%
-24.12%
7.02%
-10.53%
-0.86%
33.43%
1.31%
-19.56%
12.11%
-0.78%
7.76%
22.03%
40.51%
-16.81%
5.39%
15.40%
2.82%
7.78%
16.24%
3.45%
8.06%
2.72%
-2.22%
15.88%

Beat
Market?
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

Market
(NYSE)
8.45%
-12.53%
4.38%
-9.32%
-0.93%
3.31%
-0.91%
-0.40%
9.70%
-8.54%
7.38%
1.31%
18.11%
-12.83%
1.04%
12.05%
2.81%
7.42%
16.14%
1.59%
6.80%
2.26%
3.54%
5.28%

Sum
100%

100%

Beating the Market (Evolutionary Solver)

Quarter
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1
Q4
Q3
Q2
Q1

Year
2001
2001
2001
2001
2000
2000
2000
2000
1999
1999
1999
1999
1998
1998
1998
1998
1997
1997
1997
1997
1996
1996
1996
1996

Portfolio

Issue 8. Non-linear

AOL
-3.02%
-37.55%
32.00%
15.37%
-35.14%
1.46%
-21.37%
-11.36%
45.82%
-5.40%
-25.17%
89.52%
177.96%
6.18%
53.89%
50.96%
19.96%
35.61%
30.90%
27.82%
-6.34%
-18.86%
-21.87%
49.33%

BA
16.35%
-39.56%
0.07%
-15.34%
2.55%
54.71%
10.98%
-8.44%
-2.48%
-2.83%
29.83%
4.21%
-4.92%
-23.00%
-14.51%
6.51%
-10.10%
2.59%
7.60%
-7.39%
12.70%
8.46%
0.58%
10.53%

F
-8.54%
-28.49%
-11.80%
21.28%
-7.00%
3.66%
-6.39%
-13.83%
6.10%
-10.96%
-0.44%
-3.41%
24.87%
-20.34%
-8.94%
33.46%
7.62%
18.75%
21.12%
-2.71%
3.20%
-3.47%
-5.82%
19.05%

PG
8.77%
14.71%
2.54%
-19.80%
17.07%
18.06%
0.00%
-48.20%
16.87%
6.38%
-10.02%
7.26%
28.38%
-21.89%
7.93%
5.72%
15.57%
-2.21%
23.09%
6.62%
10.39%
7.59%
6.93%
2.11%

MCD
-1.64%
0.30%
1.92%
-21.91%
13.37%
-8.35%
-11.87%
-7.29%
-6.79%
5.17%
-9.24%
17.98%
28.69%
-13.50%
15.00%
25.65%
0.26%
-1.42%
2.25%
4.13%
-4.22%
1.34%
-2.60%
6.37%

0%
<=
19.7%
<=
100%

0%
<=
52.0%
<=
100%

0%
<=
0.2%
<=
100%

0%
<=
26.6%
<=
100%

0%
<=
1.6%
<=
100%

Number of Quarters
Beating the Market
19

Introduction to

Advantages and Disadvantages of

Evolutionary Solver

Evolutionary Solver has two significant advantages over the

standard Solver for solving difficult nonlinear programming
problems:
1.

2.

The complexity of the objective function does not matter. As long as the
function can be evaluated for a given candidate solution (to determine the level
of fitness), it does not matter if the function has kinks, discontinuities, or many
local optima.
By evaluating whole populations of candidate solutions, Evolutionary Solver
keeps from getting trapped at a local optimum. Even if the whole population
evolves toward a locally optimal solution, mutation allows the possibility of
getting unstuck.

However, Evolutionary Solver is not a panacea

It can take much longer that standard Solver to find a final solution.
Evolutionary Solver does not perform well on models that have many
constraints.

Evolutionary Solver is a random process. Running it again on the same model

usually will yield a different solution.

The best solution found is typically not optimal (although it may be very close).
Issue 8. Non-linear
Introduction to

Nonlinear Programming
Consider the following model for a
nonlinear programming problem:
maximize:
Profit = 0.5x5 6x4 + 24.5x3 39x2 + 20x
subject to:
0x5

Issue 8. Non-linear

Introduction to

Solver Solution Starting with x = 0

A
1

<=

Maximum
5

A Simple NLP

2
3
4
5
6
7

Issue 8. Non-linear

x=

0.371

Profit = 0.5x5-6x4+24.5x3-39x2+20x
=
$3.19

Introduction to

Solver Solution Starting with x = 3

A
1

<=

Maximum
5

A Simple NLP

2
3
4
5
6
7

Issue 8. Non-linear

x=

3.126

Profit = 0.5x5-6x4+24.5x3-39x2+20x
=
$6.13

Introduction to

Solver Solution Starting with x = 4.7

A
1

<=

Maximum
5

A Simple NLP

2
3
4
5
6
7

Issue 8. Non-linear

x=

5.000

Profit = 0.5x5-6x4+24.5x3-39x2+20x
=
$0.00

Introduction to

The Profit Graph

Profit($)

Issue 8. Non-linear

Introduction to

Problems that Solver will solve

correctly
A maximization problem with linear constraints
and a concave objective function.

Line
any
Line joining
joining any
twotwo
points
is on or
curve
points
is below
on orthe
below
the curve

A Concave Function

Issue 8. Non-linear

Introduction to

Problems that Solver will solve

correctly
A minimization problem with linear constraints and a convex
objective function.

Line
joining
anypoints
two
Line joining
any two
is on oris
above
points
on the
orcurve
above
the curve

A Convex Function

Issue 8. Non-linear

Introduction to

Quality Furniture Corporation

The Quality Furniture Corporation manufactures two
products: benches and tables.
They employ three carpenters. During the next week, 120
hours of labor are available at regular wages ($8 per hour).
Up to 30 hours of overtime can be used at a wage rate of
$12 per hour.
Up to 30 hours of weekend time can be utilized at a wage
rate of $16 per hour.
540 pounds of wood is available at a cost of $2 per pound.
Each bench requires 3 labor hours and 12 pounds of wood.
Each table requires 6 labor hours and 38 pounds of wood.
Completed benches sell for $80 each, and tables sell for
$200 each.

Question: How many benches and how many

tables should be produced?
Issue 8. Non-linear

Introduction to

Outdoor Furniture Labor Costs

Labor Cost
$1600
$16/hr Weekend
$1320
$12/hr Overtime
$960
$8/hr Regular

30

Issue 8. Non-linear

60

90
120
Labor Hours

Introduction to

150

180

Nonlinear Programming Spreadsheet

A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<=
<=

Available
180
540

Quality Furniture Corporation (Nonlinear)

Revenue/Unit
Labor
Wood

Benches
$85

Tables
$200

Usage per Unit Produced Total Used

3
6
135
12
38
540

Wood Cost/lb.

$2

Regular
Overtime
Sunday

Labor Cost
(per hour)
$8
$12
$16

Hours
Available
120
30
30

Production

Benches
45

Tables
0

Revenue
Wood Cost
Labor Cost
Profit

$3,825.00
$1,080.00
$1,140.00
$1,605.00

Issue 8. Non-linear

Introduction to

Outdoor Furniture Labor Costs

Labor Cost
$1600
$16/hr Weekend
$1320
$12/hr Overtime
$960
$8/hr Regular

30

Issue 8. Non-linear

60

90
120
Labor Hours

Introduction to

150

180

Separable Programming
Spreadsheet
A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

<=
<=

Available
135
540

Quality Furniture Corporation (Separable)

Revenue/Unit
Labor
Wood
Wood Cost/lb.

Benches
$85

Tables
$200

Usage per Unit Produced Total Used

3
6
135
12
38
540
$2

Regular
Overtime
Sunday

Labor Cost
(per hour)
$8
$12
$16

Hours
Available
120
30
30

Production

Benches
45

Tables
0

Labor Used
Regular Hours
120
Overtime Hours
15
Weekend Hours
0
Revenue
Wood Cost
Labor Cost
Profit

Issue 8. Non-linear

<=
<=
<=

$3,825.00
$1,080.00
$1,140.00
$1,605.00

Introduction to

120
30
30

Advertising Example
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Advertising Example (Nonlinear)

Parameters:
Unit Variable Cost
Unit Price
Salesforce Salary
Fixed Overhead
Seasonality

$48
$65
$9,000
$23,000
1.2

Decision Variable:
Advertising

$122,949

Quarter
Units Sold

Q1
14994

Sales Revenue
Cost of Sales
Gross Margin

$974,610
$719,712
$254,898

Total Fixed Costs

$154,949

Profit

$99,949

Sales (35) (Seasonality Factor) Advertising +

Issue 8. Non-linear

Introduction to

Sales Force
2

The Sales Function

Sales Force
Sales (35) (Seasonality Factor) Advertising +
2
20000
18000
16000
Sales Level

14000
12000
10000
8000
6000
4000
2000
0
0

50000

100000
Advertising

Issue 8. Non-linear

Introduction to

150000

200000

Approximating a Nonlinear Function

A
1
2
3
4
5
6
7
8
9
10
11

Approximating the Nonlinear Sales Function

Issue 8. Non-linear

Seasonality =
Sales Force =
Advertising Level
$0
$50,000
$100,000
$150,000
$200,000

1.2
9000
Sales Level
2,817
9,805
13,577
16,509
18,993

Introduction to

Slope
0.1398
0.0754
0.0586
0.0497

Advertising Example Using Separable

Programming
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

$50,000
$50,000
$0
$0
$100,000

<=
<=
<=

$50,000
$50,000
$50,000

Advertising Example (Separable)

Parameters:
Unit Variable Cost
Unit Price
Salesforce Salary
Fixed Overhead
Seasonality

$48
$65
$9,000
$23,000
1.2

Advertising ($0-$50,000)
Advertising ($50,000-$100,000)
Advertising ($100,000-$150,000)
Advertising ($150,000-)
Quarter
Units Sold

Units Sold per

Advertising Dollar
0.1398
0.0754
0.0586
0.0497
Q1
13577

Sales Revenue
Cost of Sales
Gross Margin

$882,505
$651,696
$230,809

Total Fixed Costs

$132,000

Profit

$98,809

Issue 8. Non-linear

Introduction to

Total Advertising

Evolutionary Solver
The standard Solver has difficulty with
problems that are

Highly nonlinear
Are not smooth (have kinks in the objective)
Have discontinuities (the objective jumps in value)
Have many local optima (many hills and valleys)

Excel functions like IF, MAX, ABS, ROUND, etc.,

tend to cause one or more of these problems.

Issue 8. Non-linear

Introduction to

Premium Solver
Included on the textbook CD is the
Premium Solver. After installing, a new
button (Premium) is added to Solver.

Issue 8. Non-linear

Introduction to

Premium Solver
Clicking on the Premium button switches to Premium
Solver, which gives the option of three different solvers.
Standard GRG Nonlinear is equivalent to the regular Solver without
choosing Assume Linear Model.
Standard Simplex LP is equivalent to the regular Solver with
choosing Assume Linear Model.
Standard Evolutionary uses a genetic evolutionary algorithm that is
only available with Premium Solver.

Issue 8. Non-linear

Introduction to

How Genetic Algorithms (Evolutionary

Solver) Work
Genetic algorithms (such as Evolutionary Solver) use
principles from the theory of evolution.
The Population: a large set of random solutions is
generated.
Level of fitness: each member of the population
(solution) is evaluated to determine its level of
fitness (value of objective).
Evolution: a new generation (set of solutions) is
created as follows:
Reproduction: pairs reproduce and create new solutions that share
some properties of each.
Survival of the Fittest: more fit solutions reproduce more
frequently, less fit solutions are allowed to die out.
Mutation: occasionaly random mutations are introduced.
Issue 8. Non-linear

Introduction to

Inventory Ordering Policy with Quantity

Discounts
Consider a manufacturer that orders a given part from a supplier.
They require 10,000 parts per year.
There is a cost associated with each order (due to processing,
receiving costs, fixed shipping costs, etc.) of $20.
The cost of holding a part in inventory is estimated at $4 per year.
The supplier of this part offers quantity discounts on the
purchasing cost of this part according to the following schedule.

Order Quantity Purchase Price (per

unit)
199

$10.00

100499

9.80

500999

9.70

1,0009,999

Issue 8. Non-linear

Introduction to

9.60

Total Annual Cost

Recall from Operations Management class
that the total annual cost (including
purchasing, ordering, and holding costs) is:
Total Annual Cost = Dp + (Q / 2)H + (D /
Q)S
where
D = Annual demand
p = purchase cost
Q = order size
H = annual holding cost per unit
S = ordering cost
Issue 8. Non-linear

Introduction to

Spreadsheet Model

A
1
2
3
4
5
6
7
8
9
10
11
12
13

Order Quantity

1
<=
1000
<=
20,000

Price

$9.60

Purchasing
Ordering
Holding
Total

Annual Cost
$192,000
$400
$2,000
$194,400

Ordering Policy with Quantity Discounts

Min Order
Quantity
1
100
500
1,000
10,000

Price
$10.00
$9.80
$9.70
$9.60
$9.50

Annual Demand
Ordering Cost
Annual Holding Cost

20,000
$20
$4

Issue 8. Non-linear

Introduction to

Attempts with Standard Solver

Various solutions provided by the standard
Solver, depending on the starting point:
Starting Point
(Q)
1
200
400
600
1,200
11,000
12,000
Issue 8. Non-linear

Solution (Q*)
1,000
500
447
500
1,000
10,000
1,000
Introduction to

Cost
$194,400
195,800
197,789
195,800
194,400
210,040
194,400

Cost Function with Quantity

Discounts
Cost
$230,000
$225,000
$220,000
$215,000
$210,000
$205,000
$200,000
$195,000
$190,000

10

100

447 500

1000

10,000

Order Quantity (logarithmic scale)

Issue 8. Non-linear

Introduction to

Solving with the Evolutionary Solver

A
1
2
3
4
5
6
7
8
9
10
11
12
13

Order Quantity

1
<=
1000
<=
20,000

Price

$9.60

Purchasing
Ordering
Holding
Total

Annual Cost
$192,000
$400
$2,000
$194,400

Ordering Policy with Quantity Discounts

Min Order
Quantity
1
100
500
1,000
10,000

Price
$10.00
$9.80
$9.70
$9.60
$9.50

Annual Demand
Ordering Cost
Annual Holding Cost

20,000
$20
$4

Issue 8. Non-linear

Introduction to

Tips on Using Evolutionary Solver

Bounding all of the variables greatly aids the
Evolutionary Solver by decreasing the search space.
The limit options should be increased (Max Time,
Max Subproblems, and Max Feasible Sols) for
challenging problems. Setting Tolerance to 0.0005
and Max Time Without Improvements to 30 will
ensure the algorithm will stop if the Target Cell value
has improved less than 0.05% in the last 30 seconds.
Experiment with different populations sizes and
mutation rates to see what works well. I have found
that higher than default mutation rates can be
helpful in problems with many local optima.
The Evolutionary Solver can take a very long time,
but it will usually find a good solution.
Issue 8. Non-linear

Introduction to

Tips on Using Evolutionary Solver

There is no guarantee that Evolutionary Solver will
find the best solution.
The Evolutionary Solver performs well even with
nasty objective functions, but is not very efficient at
handling constraints.
Much of the solution process is driven by random
numbers that direct the search. Thus, two people
running Evolutionary Solver on the same model may
get different results.
Once Evolutionary Solver has found a good solution,
you can use GRG Nonlinear Solver (the nonlinear
algorithm that is included with the Premium Solver
software) to try to find a slightly better solution.
Issue 8. Non-linear

Introduction to