• Overview
• Examples
• Manuals
• References

SPInE Example

Example #1: The Newsboy Problem

Problem Statement: The Informer, a newspaper having a wide circulation is interested in increasing its efficiency in distribution. The company needs to decide, every day, what is the optimal number of newspaper x to be printed in order to maximize the profits.

A deterministic formulation: This, of course, depends on the demand D for the newspaper next day. In this deterministic example, we assume that the company knows the demand with certainty. Also, there is a limit on the amount of copies that can be printed, due to the capacity of the lines. We indicate this by M. Each copy of the newspaper is characterized by a unit selling price P = 90p and a unit printing cost of C = 81p. Unsold copies e (i.e. copies printed in excess) represents a loss for the company. Moreover, if the number of copies printed is less than the demand, the company misses the opportunity to increase profits. We indicate this shortfall with h. Shortfall and excess are only revealed once the demand is known, i.e. the day after the copies have been printed. In stochastic programming jargon, this means that x is a first stage variable, while e and h are second stage variables. We can make this explicit by introducing a stage index as follows:
            t=[1,2]
where t=1 indicates today and t=2 represents tomorrow.
This index can be defined in AMPL using the following declaration:
            set time :=1..2;
The decision variables of the problem are therefore:

We can define the above decision variables in AMPL as:
            var x{t in time: t=1}>=0;
            var h{t in time: t=2}>=0;
            var e{t in time: t=2}>=0;
For the time being, we assume that the company has managed to forecast an exact value for the demand D=250. This parameter, together with the selling price P the printing cost C and the maximum amount of printable copies M are defined in AMPL as follows:
            param p:=0.9;
            param C:=0.81;
            param D:=250;
            param M:=1000;
The total profit of the company is therefore given by:
max
In AMPL this expression can be written as:
maximize
            profit: sum{t in time:t =1}(x[t]*(P-C))
            -sum{t in time:t =2}(h[t]*(P-C) + P*e[t]);
The number of copies, which can be printed, is limited by M. The following constraint expresses this bound:

which is equivalent to:
for t=1
This means that the constraint above is a first stage constraint.
In AMPL, this translates to:
subject to
            Limit{t in time: t=1}: x[t]<=M;
The number of copies printed, the excess and shortfall of copies and the demand are linked by the following balance constraint:

which can be rewritten as:
for t=2.
This second form explicitly states that the constraint can be verified when the demand is revealed, in this case in the second stage. The constraint is therefore a second stage constraint.
In AMPL, this translates to:
            Balance{t in time: t=2}: x[t-1]+h[t] - e[t] = D;
To summarise, the problem above can be implemented in AMPL as follows:
            set time := 1..2;
            param P := 0.9;
            param C := 0.81;
            param D := 250;
            param M := 1000;
            var x{t in time: t=1}>=0;
            var h{t in time: t=2}>=0;
            var e{t in time: t=2}>=0;
            maximize profit:
                        sum{t in time:t =1}(x[t]*(P-C)) -sum{t in time: t=2}(h[t]*(P-C) + P*e[t]);
            subject to
                        Limit{t in time: t=1}: x[t]<=M;
                        Balance{t in time: t=2}: x[t-1]+h[t] - e[t] = D;
Table-1:  Informer model: deterministic formulation in AMPL

Implementing and solving the model in AMPL

The following steps explain the implementation and solution of the above deterministic model using AMPL:

Step-1: Start SAMPL and Create a New Model: Start the SAMPL application, if you have not already started it. SAMPL application is started by choosing ‘New’ from the ‘File’ menu to create a new empty model file. Finally, choose’ Save As’ from the ‘File’ menu and save the model file as “informer.mod”, for data related to the model as “informer.dat”.

Step-2: Enter the model formulation for the Informer model: You are now ready to enter the model into the SAMPL. The model editor in SAMPL is a standard text editor which allows you to enter the model and perform various editing operations on the model text. In the model editor, enter the formulation of Table-1.

Step-3: Check the Syntax of the Model: After you have entered the formulation in the model editor, you can check the model for syntax errors. If SAMPL/SPInE finds a mistake in the formulation, it will report it in the Error Message window showing the erroneous line in the model, along with a short explanation of the problem. The cursor is automatically positioned at the mistake in the model file, with the offending word highlighted.
To check the syntax at the model, choose ’Check Syntax’ from the ‘Run’ menu. If there are no errors found, SAMPL will respond with a message stating that the syntax of the model is correct.  If there is an error in the model, SAMPL/SPInE will display the Error Message window.

Step-4: Solve the Model: The next step is to solve the Informer model. Solving the model involves several tasks for SAMPL/SPInE, including checking the syntax, parsing the model into memory, transferring the model to the solver, solving the model and then retrieving the solution from the solver and creating the solution file. All these tasks are done transparently to the user, when he chooses the ‘solve’ command from the menus. To solve the model follow these steps: 

1. Choose ‘Solve FortMP’ from the ‘Run’ menu or press the ‘Run Solve’ button in the Toolbar While solving the model, the Status Window appears providing you with information about the solution progress.

If everything goes well SAMPL/SPInE will display the message "Optimal Solution Found". If there is a syntax error in the error message window, check the formulation you entered from Table-1.

Step-5: Viewing and Analysing the Solution: After solving the model, SAMPL automatically creates a standard solution file containing various elements of the solution to the model. This includes, among other things, the optimal value of the objective function, the activity and reduced costs for the variables, and slack and shadow prices for the constraints. This solution file is created with the same name as the model file but with the extension .sol. In our case the solution file will be named “Informer.sol”.
After you have solved the model, you can display the solution file in a view window by pressing the Viewbutton at the bottom of the Status Window. This will display the view window shown as below.
The View Window stores the solution file in memory, allowing you to quickly browse through the solution using the scroll bars. A full listing of the solution file is shown below.

Table-2: Solutions to the informer deterministic problem

Solving Newsboy Problem with uncertain demand: The deterministic version of the Informer model is not very useful in real life. Obviously, the demand for the newspapers can be very different from the estimated value, and the number of copies to be produced needs to take into account this uncertainty. A stochastic programming approach gives us a solution which explicitly takes into account the random parameters of the problem.

Scenario generation: In stochastic programming, the uncertainty of the random parameters is introduced into the model by way of scenarios. A simple scenario generator for the Informer model can be constructed as follows:
There are three sections of the newspaper: Economics, Sports and Politics. Depending on the contents of each sections, people are more or less keen in buying the newspaper. In particular, each section may contain good, average or bad news. The following table shows how the contents influence the demand:

Table-3: Newspaper demand dependency
For instance, if each section contains good news the forecasted demand is D=195+195+195=585. The company then assigns a probability distribution to the contents of each section of the newspaper:

Table-4: Probabilities table
Assuming that the content of one section does not influence the contents of the others (i.e. they are independent random variables), the company creates the following table, which enumerates all possible combinations of the contents of the three sections, with the relating demands. The probability associated with each combination is given by the joint distribution of the individual section contents:

Table-5: Enumerated scenarios
Each row of the table represents one possible scenario for the demand. In order to reduce the computation, all the scenarios with the same value for the demand are aggregated, and their probabilities are added up. This leads to the following table, which contains the final scenarios used in the stochastic programming problem.

Table-6: Demand scenarios
The above table represents the probability distribution for the demand, which is graphically illustrated in Figure-1.


Figure-1: Distribution of the scenarios
The demand parameter D of our problem becomes therefore a vector D[s], where s represents the scenarios, with s =1..10; we also introduce a vector Prob[s], which represents the probabilities associated with each scenario.

Formulation: The Scenario generation section illustrates how the company models the uncertainty associated with the demand for the newspaper. In our example, there are 10 scenarios for the demand. The stochastic programming version of the Informer model requires therefore the definition of the scenario dimension. This can be done with the following declaration:
            scenarioset Scen;
We have shown that the demand parameter D is now a (random) vector indexed over the scenario index. The declaration of D is removed from the DATA section. In SAMPL, the random parameters of the problems are declared in the RANDOM  section. Considering Table 6, vector D can be declared as follows:
            probability param P{Scen} := 1/card(Scen);
The Informers model is a two stage recourse model. The scenario tree for a two stage can be defined very easily using the extended AMPL constructs provided by SAMPL:
            tree theTree:= twostage{2};
For more information about the declaration of the tree structure associated with a stochastic programming model, see the Tree section in the language reference.
To summarise, the stochastic programming version of the Informer model is formulated as follows:
            set time;
            scenarioset Scen
            tree theTree := twostage{2};
            param P := 0.9;
            param C := 0.81;
            param M := 1000;
            random param D{Scen} ;
            probability param P{Scen} := 1/card(Scen);
            var x{t in time: t=1}>=0;
            var h{t in time: t=2,Scen}>=0;
            var e{t in time: t=2,Scen}>=0;
            maximize profit:
                        sum{t in time:t =1} (x[t]*(P-C)) -sum{t in time: t=2} (h[t]*(P-C) + P*e[t]);
            subject to
                        Limit{t in time: t=1}: x[t]<=M;
                        Balance{t in time: t=2,s in Scen}: x[t-1]+h[t] - e[t] = D[s];

Table-7: The Informer model formulated in MPL/SAMPL

Implementing and Solving the News Boy Problem with SAMPL

The following steps explain the implementation and solution of the above stochastic model using SAMPL:

Step-1: Start SAMPL and Create a New Model: Start the SAMPL application, if you have not already started it. SAMPL application can be started by choosing ‘New’ from the ‘File’ menu to create a new empty model file. Finally, choose ‘Save As’ from the ‘File’ menu and save the file as “informerSP.mod”.

Step-2: Enter the model formulation for the stochastic Informer model: You are now ready to enter the model into SAMPL/SPInE. The model editor in SAMPL is a standard text editor which allows you to enter the model and perform various editing operations on the model text. In the model editor, enter the formulation of Table 7.

Step-3: Check the Syntax of the Model: After you have entered the formulation in the model editor, you can check the model for syntax errors. To check the syntax of a stochastic programming model, choose ‘Check Syntax’ from the ‘Stochastic’. If there are no errors found, SAMPL/SPInE will respond with a message stating that the syntax of the model is correct. If there is an error in the model, SAMPL/SPInE will display the Error Message window.

Step-4: Solve the Model: The next step is to solve the stochastic Informer model. Stochastic models are solved using the stochastic solver embedded in SAMPL. To solve the informer SP model, choose ‘Solve SAMPL’ from the ‘Stochastic’ menu. The solver can produce the solutions to the ‘Expected Value’, ‘Wait and See’ and ‘Here and Now’ problems, relating to the same model.

Step-5: Analyse the results: After solving the model, SAMPL creates one file for each solution type selected (EV, HN or WS). Also, SAMPL creates a standard SAMPL solution file, containing only the HN or EV solution. This includes among other things the optimal value of the objective function, the activity and reduced costs for the variables, and slack and shadow prices for the constraints. This solution file is created with the same name as the model file but with the extension .sol. In our case the solution file will be named “Informer.sol”.
After you have solved the model, you can display the standard SAMPL solution file in a view window by pressing the Viewbutton at the bottom of the Status Window. The SAMPL solution files, in our case “InformerSP_HN.sol”, “InformerSP_EV.sol” and “InformerSP_WS.sol” can be opened choosing the “Files” command from the “View” menu. Table 8 reports the contents of file “InformerSP_HN.sol”.

Table-8: “Here and Now” solutions of the Informer SP model