Stochastic programming

Authors: Gerald Ogbonna (gco27), Hangyu Zhou (hz477), Roohi Menon (rm832), Vikram Raghavan (vr278) (SYSEN 6800 Fall 2021)

Introduction

Stochastic Programming, also referred to as Stochastic Optimization, is a mathematical framework to help decision-making process under uncertainty [1]. With uncertainties being widespread, Stochastic Programming is a risk-neutral mathematical framework that finds application in areas, such as process systems engineering [2]. In process engineering, uncertainties are related to prices, purity of raw materials, customer demands, and yields of pilot reactors, among others. Batch processing has widely been adopted across process industries, and for the stated manufacturing process production scheduling is one of the most crucial decisions to be taken. In a deterministic optimization model, parameters, such as process of raw materials, availability of raw materials, price of different products, operation time and cost, and order demands are considered without factoring uncertainty. However, such assumptions are not realistic because uncertainty doesn’t come with a forewarning. Hence, uncertainty needs to be factored always [4].

In conventional robust optimization, the assumption is made that all decision variables are realized before the realization of uncertainty. Such an approach makes the conventional robust optimization problem overly conservative [4]. Moreover, in manufacturing not all decisions need to be made “in-the-present,” a stagnated approach to decision making [two-stage approach] can also be adopted. Going beyond, Stochastic Programming framework can also be applied to a variety of problems across sectors, such as electricity generation, financial planning, supply chain management, mitigation of climate change, and pollution control [2]. The field has evolved from deterministic linear programming by introducing random variables [7].

Theory, methodology, and/or algorithmic discussion

Two-Stage Stochastic Linear Program with Fixed Recourse:

Modeling through stochastic programming is often adopted because of its proactive-reactive decision-making feature to address uncertainty [1]. Two-stage stochastic programming (TSP) is helpful when a problem requires the analysis of policy scenarios, however, the associated system information is inherently characterized with uncertainty [2]. In a typical TSP, decision variables of an optimization problem under uncertainty are categorized into two periods. Decisions regarding the first-stage variables need to be made before the realization of the uncertain parameters. The first-stage decision variables are proactive for they hedge against uncertainty and ensure that the solution performs well under all uncertainty realizations [1]. Once the uncertain events have unfolded/realized, it is possible to further design improvements or make operational adjustments through the values of the second-stage variables, also known as recourse, at a given cost. The second-stage variables are reactive in their response to the observed realization of uncertainty [1]. Thus, optimal decisions should be made on data that is available at the time the decision is being made. In such a setup, future observations are not taken into consideration [3]. Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling [1].

Algorithm discussion:

To solve problems related to Two-Stage Linear Stochastic Programming more effectively algorithms, such as Benders decomposition or the Lagrangean decomposition can be used. Benders decomposition was presented by J.F Benders, and is a decomposition method used widely to solve mixed-integer problems. The algorithm is based on the principle of decomposing the main problem into sub-problems. The master problem is defined with only the first-stage decision variables. Once the first-stage decisions are fixed at an optimal solution of the master problem, thereafter, the subproblems are solved and valid inequalities of x are derived and added to the master problem. On solving the master problem again, the algorithm iterates until the upper and lower bound converge [2]. The Benders master problem is defined as being linear or mixed-integer and having fewer technical constraints, while the sub-problems could be linear or nonlinear in nature. The subproblems’ primary aim is to validate the feasibility of the master problem’s solution [8]. Benders decomposition is also known as L-shaped decomposition because once the first stage variables, x, are fixed then the rest of the problem has a structure of a block-diagonal. This structure can be decomposed by scenario and solved independently [2].

Numerical Example:

The farmer example and solution approach, for two-stage stochastic programming, is from Birge & Louveaux’s book on stochastic optimization (2011) [16]. The initial problem statement is solved using a linear programming solver. However, this method fails to consider variability with respect to yields which is highly linked to weather conditions. Crop yields for a year can be termed as below average, average and above average. Yields have been fixed as 20% above and below the average given this, the farmer would like to understand how sensitive the optimal solution is to variations in yields. To address this, two optimization models – above average and below average- have been framed and executed.  

Results from the two models suggest that when yields are high a small surface is sufficient to meet the minimum production requirement. However, when yields are low larger surface areas are needed to meet the minimum production requirement. In fact, with low yields corn must be purchased from the market to meet requirements. Thus, the key takeaway being that the optimal solution is sensitive to changes in yields. The farmer would benefit tremendously if they had access to the weather forecast. But, given the absence of perfect information the farmer must take a decision based on the existing data.  

Among all the three crops, i.e., wheat, corn and sugar beets, making a decision pertaining to sugar beets cultivation seems difficult for the farmer. On the one hand, if the farmer were to dedicate large surface areas to sugar beet cultivation the farmer would certainly meet the requirement and sell at the quota, but would also have to sell the excess amount of sugar beets at the unfavorable price. On the other hand, if small surface areas were dedicated to sugar beet cultivation, then the farmer would miss the opportunity of selling at the quota (favorable) price. In the stated situation, the farmer realizes that a perfect decision cannot be taken - a decision that would work in all possible scenarios. The farmer would like to evaluate the benefits and losses of every decision at each stage, and to do so adopts the two-stage stochastic linear programming approach.

In the first stage, decisions that are to be taken ‘now’, are those pertaining to land assignment of each crop. Let land assignment to wheat be ‘x1’, land assignment to corn be ‘x2’ and land assignment to sugar beets be ‘x3’. While decisions pertaining to sales and purchases depend on the yield. The second-stage variables can be indexed based on scenarios, where ‘s1’ corresponds to above average yields, ‘s2’ corresponds to average yields and ‘s3’ corresponds to below average yields. If the farmer seeks to maximize long-run profit then the three defined scenarios have an equal probability of 1/3. Given how explicitly the second- stage variables have been defined, this problem can be considered as an extensive form of stochastic programming. Having stated the approach, the problem can be formulated as given below:

𝑚𝑖𝑛 150𝑥1 + 230𝑥2 + 260𝑥3 − 13(170𝑤11 − 238𝑦11 + 150𝑤21 − 210𝑦21 + 36𝑤31 + 10𝑤41) − 13(170𝑤12 − 238𝑦12 + 150𝑤22 − 210𝑦22 + 36𝑤32 + 10𝑤42) − 13(170𝑤13 − 238𝑦13 + 150𝑤23 − 210𝑦23 + 36𝑤33 + 10𝑤43)

𝑠. 𝑡.

𝑥1 +𝑥2 +𝑥3 ≤ 500;

3𝑥1 + 𝑦11 − 𝑤11 ≥ 200;

3.6𝑥2 + 𝑦21 − 𝑤21 ≥ 240;

𝑤31 + 𝑤41 ≤ 24𝑥3; 𝑤31 ≤ 6000;

2.5𝑥1 + 𝑦12 + 𝑤12 ≥ 200;

3𝑥2 + 𝑦22 − 𝑤22 ≥ 240;

𝑤32 + 𝑤42 ≤ 20𝑥3;

𝑤32 ≤ 6000;

2𝑥1 + 𝑦13 − 𝑤13 ≥ 200;

2.4𝑥2 + 𝑦23 − 𝑤23 ≥ 240;

𝑤33 + 𝑤43 ≤ 16𝑥3;

𝑤33 ≤ 6000;

𝑥,𝑦,𝑤 ≥ 0

		Wheat	Corn	Sugar beets
First decision	Area in terms of Acres	170	80	250
s=1 (above average yield)	Yield (t)	510	288	6000
	Sales (t)	310	48	6000 (favorable price)
	Purchase (t)	-	-	-
s=2 (average yield)	Yield (t)	425	240	5000
	Sales (t)	225	-	5000 (favorable price)
	Purchase (t)	-	-	-
s=3 (below average yield)	Yield (t)	340	192	4000
	Sales (t)	140	-	4000(favorable price)
	Purchase (t)	-	48
Overall profit ($)	108,390

Table A: Solution from the two-stage linear stochastic model.

The solution showcases a key aspect, under uncertainty finding a solution that works for all circumstances is quite not possible. For one, the farmer would always have to decide on the trade-off between selling some sugar beets at an unfavorable price or having some unused quota. Such a predicament would never arise if the farmer had access to a perfect weather forecast. Given the uncertainty, stochastic programming helps model balanced decisions