Case Study: The Surfboard Production Problem

Submitted: 8 Feb 2008

Operations Research Topics: NonlinearProgramming

Application Areas: Sports Equipment Manufacturing

Contents

Problem Description

A surfboard manufacturer is planning his monthly surfboard production of Malibu and Super Thruster boards. He has limitations on his supply of fibreglass resin, having only 72 kilos left in stock. To construct a Malibu board requires 3 kilos of resin, and to build a Super Thruster one needs 4 kilos.

He has consulted a market research firm about the effect of the price he charges on the demand for the surfboards. They have provided him with the following information. If the price of a Malibu board is $p_M$ and the price of a Super Thruster board is $p_S$, then the demands for the two types of boards ($d_M$ and $d_S$ respectively) are given by:

 \begin{align*} d_M &= 12000 p_M^{-1.5} \\ d_S &= 12000 p_S^{-1.8} \end{align*}

The manufacturer would like to know how much he should charge for his boards and which boards to make in order to maximize his return (the money he makes) from board sales.

Return to top

Problem Formulation

To formulate this problem we will use the 4 steps for formulating a mathematical programme.

1. Identify the Decision Variables

The manufacturer has two decisions to make:
  1. the price to charge for the surfboards;
  2. how many surfboards to make.

Define the set of types of surfboards to make ${\cal S}$ and then define the decision variables:

 \begin{align*} p_s &= \text{price of surfboard type $s$} \\ x_s &= \text{production amount for surfboard type $s$} \end{align*}

2. Formulate the Objective Function

The manufacturer wants to maximise his return from selling the surfboards. He does not want to have any left over as that is a waste of resin, so he will not make enough boards to satisfy demand. Thus, he assumes he will sell all the boards he makes. His return will be the number of boards of each type he makes multiplied by the price he chooses for that type of board:
\[ \max \sum_{s \in {\cal S}} p_s x_s \]

3. Formulate the Constraints

The manufacturer only has 72 kilograms of resin to make his boards. Define a set of raw materials ${\cal M}$ and $U_m$ as the upper limit of each raw material available (for this example ${\cal M} = \{ \text{resin} \}$ and $U_\text{resin} = 72$. Also, define $r_{ms}$ as the amount of raw material $m$ required (in kg) to make a surfboard of type $s$. The manufacturing constraints are:
\[ \sum_{s \in {\cal S}} r_{ms} x_s \leq U_m, m \in {\cal M} \]
For this example
\[ 4 x_\text{Malibu} + 3 x_\text{Super Thruster} \leq 72 \]
for resin.

Furthermore, he does not believe he will sell more than the estimated demand, i.e., $x_s \leq d_s, s \in {\cal S}$, where $d_s$ is defined by the market research equations. Thus, he won't make more than those estimates.

Finally, he cannot sell a negative number of boards, i.e., $x_s \geq 0, s \in {\cal S}$ and he can only sell an integer number of boards, i.e., $x_s \in {\mathbb Z}, s \in {\cal S}$.

The complete formulation is:

 \begin{align*} \max \sum_{s \in {\cal S}} p_s & x_s \\ \sum_{s \in {\cal S}} r_{ms} & x_s \leq U_m, m \in {\cal M} \\ & x_s \leq C_s  {p_s}^{E_s} \\ & x_s \geq 0, \in {\mathbb Z} \end{align*}

where $C_s$ and $E_s$ are the coefficient and exponent of the demand expression for surfboard $s$ respectively.

Return to top

Computational Model

To build our mathematical programme in AMPL we first define the sets for surfboards ${\cal S}$ and raw materials ${\cal M}$ in surfboard.mod:

set SURFBOARDS;
set MATERIALS;

Next, we add the parameters for surfboards $C_s, E_s, s \in {\cal S}$ to surfboard.mod:

param Coefficient {SURFBOARDS};
param Exponent {SURFBOARDS};

As well as the parameters for raw materials:

param Supply {MATERIALS};
and for the surfboard "recipe"
param Recipe {MATERIALS, SURFBOARDS};

Our final step, before implementing our formulation in surfboard.mod is to define the decision variables:

var Price {SURFBOARDS};
var Production {SURFBOARDS} >= 0, integer;

Now the formulation is straightforward:

maximize TotalProfit:
  sum {s in SURFBOARDS} Price[s] * Production[s];

subject to MaterialSupply {m in MATERIALS} :
  sum {s in SURFBOARDS} Recipe[m, s] * Production[s] <= Supply[m];

subject to SurfboardDemand {s in SURFBOARDS} :
  Production[s] <= Coefficient[s] * (Price[s] ^ Exponent[s]);

Note Both the objective and the SurfboardDemand are nonlinear expressions.

The formulation data is specified in surfboard.dat. The sets are straightforward (note the use of ' to define the whitespace in Super Thruster):

set SURFBOARDS := Malibu 'Super Thruster' ;
set MATERIALS  := Resin ;
and by defining multiple parameters at once we can define the demand equation parameters at the same time:
param:           Coefficient Exponent :=
 Malibu                12000     -1.5
'Super Thruster'       12000     -1.8 ;

Using a list to define the Supply parameter and a table to define the Recipe parameter completes surfboard.dat:

param Supply :=
Resin     72 ;

param Recipe :
      Malibu 'Super Thruster' :=
Resin      3               4 ;

Since our mathematical programme is a nonlinear programme we cannot use CPLEX to solve our problem. In (the Student Edition) of AMPL we can use MINOS for nonlinear programming. The script file for solving this problem would typically be similar to:

reset;

model surfboard.mod;
data surfboard.dat;

option solver minos;
solve;

display Price, Production;

However, if you run this script file you will observe the following error:

minos_error.jpg

This error occurs because the initial values for Price (and Production) are set to 0. Both demand estimation functions have negative exponents, so are undefined for a value of 0, i.e.,

\[ 0^{-1.5} = \frac{1}{0^{1.5}} \qquad 0^{-1.8} = \frac{1}{0^{1.8}} \]

both of which are undefined.

We can set the initial values of the Price variables to be non-zero:

let Price['Malibu'] := 1;
let Price['Super Thruster'] := 1;
and resolve:

minos_fix.jpg

Note that MINOS does not actually solve for integer variables:

MINOS 5.5: ignoring integrality of 2 variables
but both the Production variables both have integer values.

MINOS also terminated before determining optimality

MINOS 5.5: too many major iterations.

By default, the number of major iterations allowed by MINOS is 50. If you increase the number of major iterations by changing the MINOS options:

option minos_options 'major_iterations=100';
and resolve you will notice that the price of the Super Thruster board is slowly increasing, as is the total return. By increasing the limit on the major iterations to 1500 we get the optimal solution:

minos_itns.jpg

Return to top

Results

Our computational model shows that the optimal solution is to produce 24 Super Thruster boards and sell them for $31.5811 each. Note that this solution yields integer production values, but the optimal prices ($31.958 for the Super Thruster boards and $1.01 for the Malibu boards) seem low. We may have encountered a local optimum.

If the manufacturer only makes Malibu boards he has enough resin to make 18 boards. To get demand for 18 boards his price

 \begin{equation*} p_\text{Malibu} = \left(\frac{12000}{18}\right)^{\frac{1}{1.5}} = \$76.31. \end{equation*}

If the manufacturer only makes Super Thruster boards he has enough resin to make 24 boards. To get demand for 24 boards his price

 \begin{equation*} p_\text{Super Thruster} = \left(\frac{12000}{24}\right)^{\frac{1}{1.8}} = \$31.58. \end{equation*}

Let's try these prices as initial values in surfboard.run:

minos_opt.jpg

This gives us a different optimal solution with a much higher return $1665.27. However, this solution does not give us integer production. Unfortunately, MINOS does not solve for integer variables. However, MINLP on the NEOS server will solve nonlinear programmes with integer variables. Furthermore, MINLP (on NEOS) accepts AMPL input. We can use surfboard.mod and surfboard.dat as the model and data files and revise our script file

let Price['Malibu'] := 101.27;
let Price['Super Thruster'] := 56.96;

solve;

display Price, Production;
to solve using MINLP (on the NEOS Server) and find an optimal integer solution.

You are using the solver minlp.
Executing AMPL.
processing data.
processing commands.

4 variables, all nonlinear
3 constraints; 6 nonzeros
	2 nonlinear constraints
	1 linear constraint
1 nonlinear objective; 4 nonzeros.

MINLP-B&B (20020703): m(before SOS) = 3
m(a f t e r SOS) = 3
Optimal solution found
3 subproblems, objective = 1665.141545
Evals: obj = 107, constr = 107, grad = 46, Hes = 45
:                   Price   Production    :=
Malibu             100           12
'Super Thruster'    58.1427       8
;

The manufacturer will most likely want a price that is to the nearest cent. It is dangerous to round mathematical programme solutions as even a small change in the variable value may result in a large change in the objective function or may even cause the solution to become infeasible. Since the Price variables cause our mathematical programme to be nonlinear, we will fix these variables and use CPLEX to solve for the Production variables:

reset;

model surfboard.mod;
data surfboard.dat;

option solver cplex;

let Price['Malibu'] := 100;
let Price['Super Thruster'] := 58.14;

fix Price;

solve;

display Price, Production;

let Price['Malibu'] := 100;
let Price['Super Thruster'] := 58.15;

fix Price;

solve;

display Price, Production;

Note that we rounded both up and down to check the "local neighbourhood" of the optimal point (see some discussion about solution accuracy).

cplex_opt.jpg

Return to top

Conclusions

The Surfboard Production problem is a relatively simple problem to formulate, but its solution requires careful thought and analysis. The management summary surfboard.doc contains some information about the initial values used (so future consultants/researchers can follow the work) and details about the NEOS Optimization Server.

Return to top

Extra for Experts

Examining the Objective Function

The nonlinearity in this problem is introduced by the price variables. If these variables are fixed we can use CPLEX to find the optimal production levels. By looping over possible pairs of values for the prices and solving for the production levels we can build up a picture of the objective function.

param Objective {1..150, 1..150};

fix Price;

for {p in 1..150 by 1, q in 1..150 by 1} {
  let Price['Malibu'] := p;
  let Price['Super Thruster'] := q;
  
  option solver cplex;
  solve;

  let Objective[p, q] := TotalProfit;
}

Using this picture we can try to discern if the optimal solution we found using MINLP (shown below) is the global optimum.

:                   Price   Production    :=
Malibu             100           12
'Super Thruster'    58.1427       8

Hint This for loop may take a long time to finish. Also, you may want to print the TotalProfit parameter to a file using AMPL.

Return to top

Student Tasks

  1. Try different initial values for both Price and Production. Do you believe that the MINLP solution is the global optimum?

    What to hand in Hand in a summary of your different experiments along with an answer to the global optimality question. Be sure to justify your answer.

  2. Experts Only Use AMPL and CPLEX to create a picture of the objective function. Does the solution we found using MINLP look like the global optimum?

    What to hand in Your picture of the objective function. Your answer to the global optimality questions. Be sure to justify your answer.

Return to top

Topic attachments
I Attachment History Action Size Date Who Comment
Unknown file formatdat surfboard.dat r1 manage 0.3 K 2008-03-18 - 10:24 TWikiAdminUser  
Microsoft Word filedoc surfboard.doc r2 r1 manage 26.0 K 2009-10-09 - 01:19 MichaelOSullivan  
Unknown file formatmod surfboard.mod r2 r1 manage 1.0 K 2008-03-18 - 20:58 MichaelOSullivan  
Unknown file formatrun surfboard.run r1 manage 0.4 K 2008-03-18 - 10:24 TWikiAdminUser  
Edit | Attach | Watch | Print version | History: r29 < r28 < r27 < r26 < r25 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r29 - 2018-11-23 - TWikiAdminUser
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback