Stochastic programming - Revision history

Hangyu: /* Algorithm discussion */

2021-12-16T04:59:12Z

Algorithm discussion

← Older revision		Revision as of 00:59, 16 December 2021
Line 30:		Line 30:
	=== Algorithm discussion ===		=== Algorithm discussion ===

	To solve problems related to Two-Stage Linear Stochastic Programming more effectively, algorithms such as ~~[[Wikipedia:~~ Benders decomposition~~\|Benders decomposition]]~~ or the Lagrangean decomposition can be used. Benders decomposition was presented by ~~[[Wikipedia: Jacques F. Benders\|~~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. <ref name=":0" /> 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. <ref name=":5" /> Benders decomposition is also known as L-shaped decomposition because once the first stage variables, <math>x</math>, 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. <ref name=":0" />		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. <ref name=":0" /> 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. <ref name=":5" /> Benders decomposition is also known as L-shaped decomposition because once the first stage variables, <math>x</math>, 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. <ref name=":0" />

	...		...
	We assume that the random vector <math>\xi</math> has finite ~~[[Wikipedia: Support (mathematics)\|~~support]]. Let <math>k=1,\ldots,K</math> index possible second stage realizations and let <math>p_k</math> be the corresponding probabilities. With that, we could write down the deterministic equivalent of the stochastic program. This form is created by associating one set of second-stage decisions (<math>y_k</math>) to each realization of <math>\xi</math>, i.e., to each realization of <math>q_k</math>, <math>h_k</math>, and <math>T_k</math>. This large-scale deterministic counterpart of the original stochastic program is known as the ''extensive form'':		We assume that the random vector <math>\xi</math> has finite support. Let <math>k=1,\ldots,K</math> index possible second stage realizations and let <math>p_k</math> be the corresponding probabilities. With that, we could write down the deterministic equivalent of the stochastic program. This form is created by associating one set of second-stage decisions (<math>y_k</math>) to each realization of <math>\xi</math>, i.e., to each realization of <math>q_k</math>, <math>h_k</math>, and <math>T_k</math>. This large-scale deterministic counterpart of the original stochastic program is known as the ''extensive form'':

	<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">		<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">

Hangyu: /* Applications */

2021-12-16T04:57:29Z

Applications

← Older revision		Revision as of 00:57, 16 December 2021
Line 308:		Line 308:

	== Applications ==		== Applications ==
	Apart from the process industry, two-stage linear stochastic programming finds application in other fields as well. For instance, in the optimal design of distributed energy systems, there are various uncertainties that need to be considered. Uncertainty is related to aspects such as demand and supply of energy, economic factors like unit investment cost and energy price, and uncertainty related to technical parameters like efficiency~~. Zhou et al~~. <ref name=":7">Zhe Zhou, Jianyun Zhang, Pei Liu, Zheng Li, Michael C. Georgiadis, Efstratios N. Pistikopoulos, [https://doi.org/10.1016/j.apenergy.2012.09.019 “A two-stage stochastic programming model for the optimal design of distributed energy systems,”] ''Applied Energy'', Volume 103, 2013, Pages 135-144, ISSN 0306-2619.</ref>, developed a two-stage stochastic programming model for the optimal design of a distributed energy system with a stage decomposition-based solution strategy. The authors accounted for both demand and supply uncertainty. They used the genetic algorithm on the first stage variables and the Monte Carlo method on the second-stage variables.		Apart from the process industry, two-stage linear stochastic programming finds application in other fields as well. For instance, in the optimal design of distributed energy systems, there are various uncertainties that need to be considered. Uncertainty is related to aspects such as demand and supply of energy, economic factors like unit investment cost and energy price, and uncertainty related to technical parameters like efficiency. <ref name=":7">Zhe Zhou, Jianyun Zhang, Pei Liu, Zheng Li, Michael C. Georgiadis, Efstratios N. Pistikopoulos, [https://doi.org/10.1016/j.apenergy.2012.09.019 “A two-stage stochastic programming model for the optimal design of distributed energy systems,”] ''Applied Energy'', Volume 103, 2013, Pages 135-144, ISSN 0306-2619.</ref>, developed a two-stage stochastic programming model for the optimal design of a distributed energy system with a stage decomposition-based solution strategy. The authors accounted for both demand and supply uncertainty. They used the genetic algorithm on the first stage variables and the Monte Carlo method on the second-stage variables.

	Another application of the two-stage linear stochastic programming is in the bike-sharing system (BSS). The system needs to ensure that bikes are available at all stations per the given demand. To ensure this balance, redistribution trucks are used to transfer bikes from one bike surplus station to a bike deficient station. Such a problem is referred to as the bike repositioning problem (BRS) in the aforementioned system. <ref name=":8">Qiong Tang, Zhuo Fu, Dezhi Zhang, Hao Guo, Minyi Li, [https://doi.org/10.1155/2020/8868892 "Addressing the Bike Repositioning Problem in Bike Sharing System: A Two-Stage Stochastic Programming Model,"] ''Scientific Programming'', vol. 2020, Article ID 8868892, 12 pages, 2020.</ref> Another challenge related to BRP is the aspect related to the holding cost of the depot. While transferring bikes from one station to another they could get damaged or be lost in the process which could lead to an imbalance between demand and supply in the BSS. As for bikes that cannot be balanced among the stations of the BSS are either placed back at the depot at increase the holding cost of the depot. To address the stated concerns, ~~Tang et al <ref name=":8" />,~~ developed a two-stage stochastic program that would capture the uncertainty related to redistribution of demand within the system. In the first stage, before the realization of redistribution demand, a decision regarding routing was made. In the second stage, decisions regarding loading/unloading at each station and depot are made. Holding cost is incorporated into the model, such that the model’s primary objective is to determine the best routes of the repositioning truck and the optimal loading/unloading quantities at each station and depot. The model is framed to minimize the expected total sum of transportation cost, the penalty cost of all stations, and the holding cost of the depot.		Another application of the two-stage linear stochastic programming is in the bike-sharing system (BSS). The system needs to ensure that bikes are available at all stations per the given demand. To ensure this balance, redistribution trucks are used to transfer bikes from one bike surplus station to a bike deficient station. Such a problem is referred to as the bike repositioning problem (BRS) in the aforementioned system. <ref name=":8">Qiong Tang, Zhuo Fu, Dezhi Zhang, Hao Guo, Minyi Li, [https://doi.org/10.1155/2020/8868892 "Addressing the Bike Repositioning Problem in Bike Sharing System: A Two-Stage Stochastic Programming Model,"] ''Scientific Programming'', vol. 2020, Article ID 8868892, 12 pages, 2020.</ref> Another challenge related to BRP is the aspect related to the holding cost of the depot. While transferring bikes from one station to another they could get damaged or be lost in the process which could lead to an imbalance between demand and supply in the BSS. As for bikes that cannot be balanced among the stations of the BSS are either placed back at the depot to increase the holding cost of the depot. To address the stated concerns, researchers developed a two-stage stochastic program that would capture the uncertainty related to redistribution of demand within the system. <ref name=":8" /> In the first stage, before the realization of redistribution demand, a decision regarding routing was made. In the second stage, decisions regarding loading/unloading at each station and depot are made. Holding cost is incorporated into the model, such that the model’s primary objective is to determine the best routes of the repositioning truck and the optimal loading/unloading quantities at each station and depot. The model is framed to minimize the expected total sum of transportation cost, the penalty cost of all stations, and the holding cost of the depot.

	== Conclusion ==		== Conclusion ==

Hangyu at 04:47, 16 December 2021

2021-12-16T04:47:38Z

← Older revision		Revision as of 00:47, 16 December 2021
Line 13:		Line 13:

	=== Methodology ===		=== Methodology ===
	The classical two-stage stochastic linear program with fixed recourse <ref name=":7" /> is given below:		The classical two-stage stochastic linear program with fixed recourse <ref name=":5">Soares, Joao, et al. [https://doi.org/10.1109/tia.2017.2723339 “Two-Stage Stochastic Model Using Benders’ Decomposition for Large-Scale Energy Resource Management in Smart Grids.”] ''IEEE Transactions on Industry Applications'', vol. 53, no. 6, 2017, pp. 5905–5914.</ref> is given below:

	<math> \min z=c^Tx + E_{\xi}[\min q(\omega)^Ty(\omega)] </math>		<math> \min z=c^Tx + E_{\xi}[\min q(\omega)^Ty(\omega)] </math>
Line 25:		Line 25:
	Where <math>c</math> is a known vector in <math>\mathbb{R}^{n_1}</math>, <math>b</math> is a known vector in <math>\mathbb{R}^{m_1}</math>. <math>A</math> and <math>W</math> are known matrices of size <math>m_1 \times n_1</math> and <math>m_2 \times n_2</math> respectively. <math>W</math> is known as the recourse matrix.		Where <math>c</math> is a known vector in <math>\mathbb{R}^{n_1}</math>, <math>b</math> is a known vector in <math>\mathbb{R}^{m_1}</math>. <math>A</math> and <math>W</math> are known matrices of size <math>m_1 \times n_1</math> and <math>m_2 \times n_2</math> respectively. <math>W</math> is known as the recourse matrix.

	The first-stage decisions are represented by the <math>n_1 \times 1</math> vector <math>x</math>. Corresponding to <math>x</math> are the first-stage vectors and matrices <math>c</math>, <math>b</math>, and <math>A</math>. In the second stage, a number of random events <math>\omega \in \Omega</math> may realize. For a given realization <math>\omega</math>, the second-stage problem data <math>q(\omega)</math>, <math>h(\omega)</math>, and <math>T(\omega)</math> become known. <ref name=":10" />		The first-stage decisions are represented by the <math>n_1 \times 1</math> vector <math>x</math>. Corresponding to <math>x</math> are the first-stage vectors and matrices <math>c</math>, <math>b</math>, and <math>A</math>. In the second stage, a number of random events <math>\omega \in \Omega</math> may realize. For a given realization <math>\omega</math>, the second-stage problem data <math>q(\omega)</math>, <math>h(\omega)</math>, and <math>T(\omega)</math> become known. <ref name=":6">Birge, John R., and François Louveaux. [https://link.springer.com/book/10.1007/978-1-4614-0237-4 "Introduction to Stochastic Programming."] Springer, 2011. </ref>


	=== Algorithm discussion ===		=== Algorithm discussion ===

	To solve problems related to Two-Stage Linear Stochastic Programming more effectively, algorithms such as [[Wikipedia: Benders decomposition\|Benders decomposition]] or the Lagrangean decomposition can be used. Benders decomposition was presented by [[Wikipedia: Jacques F. Benders\|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. <ref name=":1" /> 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. <ref name=":7">Soares, J., Canizes, B., Ghazvini, M. A. F., Vale, Z., & Venayagamoorthy, G. K. (2017). Two-stage stochastic model using benders’ decomposition for large-scale energy resource management in smart grids. IEEE Transactions on Industry Applications, 53(6), 5905-5914.</~~ref~~> Benders decomposition is also known as L-shaped decomposition because once the first stage variables, <math>x</math>, 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. <ref name=":1" />		To solve problems related to Two-Stage Linear Stochastic Programming more effectively, algorithms such as [[Wikipedia: Benders decomposition\|Benders decomposition]] or the Lagrangean decomposition can be used. Benders decomposition was presented by [[Wikipedia: Jacques F. Benders\|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. <ref name=":0" /> 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. <ref name=":5" /> Benders decomposition is also known as L-shaped decomposition because once the first stage variables, <math>x</math>, 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. <ref name=":0" />

	...		...
Line 48:		Line 48:
	It is equivalent with the following formulation. The L-shape block structure of this extensive form gives rise to the name, L-shaped method.		It is equivalent with the following formulation. The L-shape block structure of this extensive form gives rise to the name, L-shaped method.
	<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">		<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
	[[File:Lshape.png\|thumb\|200px\|Block structure of the two-stage extensive form <ref name=":10" />]]		[[File:Lshape.png\|thumb\|200px\|Block structure of the two-stage extensive form <ref name=":6" />]]
	<math>		<math>
	\begin{array}{lccccccccccccc}		\begin{array}{lccccccccccccc}
Line 308:		Line 308:

	== Applications ==		== Applications ==
	Apart from the process industry, two-stage linear stochastic programming finds application in other fields as well. For instance, in the optimal design of distributed energy systems, there are various uncertainties that need to be considered. Uncertainty is related to aspects such as demand and supply of energy, economic factors like unit investment cost and energy price, and uncertainty related to technical parameters like efficiency. Zhou et al. <ref name=":8">Zhe Zhou, Jianyun Zhang, Pei Liu, Zheng Li, Michael C. Georgiadis, Efstratios N. Pistikopoulos, “A two-stage stochastic programming model for the optimal design of distributed energy systems,” Applied Energy, Volume 103, 2013, Pages 135-144, ISSN 0306-2619~~, <nowiki>https://doi.org/10.1016/j.apenergy.2012.09.019</nowiki>~~.</ref>, developed a two-stage stochastic programming model for the optimal design of a distributed energy system with a stage decomposition-based solution strategy. The authors accounted for both demand and supply uncertainty. They used the genetic algorithm on the first stage variables and the Monte Carlo method on the second-stage variables.		Apart from the process industry, two-stage linear stochastic programming finds application in other fields as well. For instance, in the optimal design of distributed energy systems, there are various uncertainties that need to be considered. Uncertainty is related to aspects such as demand and supply of energy, economic factors like unit investment cost and energy price, and uncertainty related to technical parameters like efficiency. Zhou et al. <ref name=":7">Zhe Zhou, Jianyun Zhang, Pei Liu, Zheng Li, Michael C. Georgiadis, Efstratios N. Pistikopoulos, [https://doi.org/10.1016/j.apenergy.2012.09.019 “A two-stage stochastic programming model for the optimal design of distributed energy systems,”] ''Applied Energy'', Volume 103, 2013, Pages 135-144, ISSN 0306-2619.</ref>, developed a two-stage stochastic programming model for the optimal design of a distributed energy system with a stage decomposition-based solution strategy. The authors accounted for both demand and supply uncertainty. They used the genetic algorithm on the first stage variables and the Monte Carlo method on the second-stage variables.

	Another application of the two-stage linear stochastic programming is in the bike-sharing system (BSS). The system needs to ensure that bikes are available at all stations per the given demand. To ensure this balance, redistribution trucks are used to transfer bikes from one bike surplus station to a bike deficient station. Such a problem is referred to as the bike repositioning problem (BRS) in the aforementioned system. <ref name=":9">Qiong Tang, Zhuo Fu, Dezhi Zhang, Hao Guo, Minyi Li, "Addressing the Bike Repositioning Problem in Bike Sharing System: A Two-Stage Stochastic Programming Model", Scientific Programming, vol. 2020, Article ID 8868892, 12 pages, 2020.~~<nowiki>https://doi.org/10.1155/2020/8868892</nowiki>~~		Another application of the two-stage linear stochastic programming is in the bike-sharing system (BSS). The system needs to ensure that bikes are available at all stations per the given demand. To ensure this balance, redistribution trucks are used to transfer bikes from one bike surplus station to a bike deficient station. Such a problem is referred to as the bike repositioning problem (BRS) in the aforementioned system. <ref name=":8">Qiong Tang, Zhuo Fu, Dezhi Zhang, Hao Guo, Minyi Li, [https://doi.org/10.1155/2020/8868892 "Addressing the Bike Repositioning Problem in Bike Sharing System: A Two-Stage Stochastic Programming Model,"] ''Scientific Programming'', vol. 2020, Article ID 8868892, 12 pages, 2020.</ref> Another challenge related to BRP is the aspect related to the holding cost of the depot. While transferring bikes from one station to another they could get damaged or be lost in the process which could lead to an imbalance between demand and supply in the BSS. As for bikes that cannot be balanced among the stations of the BSS are either placed back at the depot at increase the holding cost of the depot. To address the stated concerns, Tang et al <ref name=":8" />, developed a two-stage stochastic program that would capture the uncertainty related to redistribution of demand within the system. In the first stage, before the realization of redistribution demand, a decision regarding routing was made. In the second stage, decisions regarding loading/unloading at each station and depot are made. Holding cost is incorporated into the model, such that the model’s primary objective is to determine the best routes of the repositioning truck and the optimal loading/unloading quantities at each station and depot. The model is framed to minimize the expected total sum of transportation cost, the penalty cost of all stations, and the holding cost of the depot.
	</ref> Another challenge related to BRP is the aspect related to the holding cost of the depot. While transferring bikes from one station to another they could get damaged or be lost in the process which could lead to an imbalance between demand and supply in the BSS. As for bikes that cannot be balanced among the stations of the BSS are either placed back at the depot at increase the holding cost of the depot. To address the stated concerns, Tang et al <ref name=":9" />, developed a two-stage stochastic program that would capture the uncertainty related to redistribution of demand within the system. In the first stage, before the realization of redistribution demand, a decision regarding routing was made. In the second stage, decisions regarding loading/unloading at each station and depot are made. Holding cost is incorporated into the model, such that the model’s primary objective is to determine the best routes of the repositioning truck and the optimal loading/unloading quantities at each station and depot. The model is framed to minimize the expected total sum of transportation cost, the penalty cost of all stations, and the holding cost of the depot.

	== Conclusion ==		== Conclusion ==
	From the previous examples, it is evident that two-stage linear stochastic programming finds applicability across many areas, such as the petrochemical, pharmaceutical industry, carbon capture, and energy storage among others. <ref name=":1" /> Stochastic programming can primarily be used to model two types of uncertainties: 1) exogenous uncertainty, which is the most widely considered one, and 2) endogenous uncertainty, where realization regarding uncertainty depends on the decision taken. The main challenge, with respect to stochastic programming, is that the type of problems that can be solved is limited. An ‘ideal’ problem would be multi-stage stochastic mixed-integer nonlinear programming under both exogenous and endogenous uncertainty with an arbitrary probability distribution that is stagewise dependent. <ref name=":1" /> However, current algorithms, in terms of development and computation resources, are still limited with respect to the ability to solve the ‘ideal’ problem.		From the previous examples, it is evident that two-stage linear stochastic programming finds applicability across many areas, such as the petrochemical, pharmaceutical industry, carbon capture, and energy storage among others. <ref name=":0" /> Stochastic programming can primarily be used to model two types of uncertainties: 1) exogenous uncertainty, which is the most widely considered one, and 2) endogenous uncertainty, where realization regarding uncertainty depends on the decision taken. The main challenge, with respect to stochastic programming, is that the type of problems that can be solved is limited. An ‘ideal’ problem would be multi-stage stochastic mixed-integer nonlinear programming under both exogenous and endogenous uncertainty with an arbitrary probability distribution that is stagewise dependent. <ref name=":0" /> However, current algorithms, in terms of development and computation resources, are still limited with respect to the ability to solve the ‘ideal’ problem.

	== References ==		== References ==

Hangyu: /* Theory, methodology, and/or algorithmic discussion */

2021-12-16T04:31:33Z

Theory, methodology, and/or algorithmic discussion

← Older revision		Revision as of 00:31, 16 December 2021
Line 10:		Line 10:
	== Theory, methodology, and/or algorithmic discussion ==		== Theory, methodology, and/or algorithmic discussion ==

	Modeling through stochastic programming is often adopted because of its proactive-reactive decision-making feature to address uncertainty. <ref name=":3"> Chu, Yunfei, and Fengqi You. [https://doi.org/10.1021/ie402621t “Integration of Scheduling and Dynamic Optimization of Batch Processes under Uncertainty: Two-Stage Stochastic Programming Approach and Enhanced Generalized Benders Decomposition Algorithm.”] ''Industrial & Engineering Chemistry Research'', vol. 52, no. 47, 2013, pp. 16851–16869.</ref> 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. <ref name=":1" /> 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. <ref name=":0" /> 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. <ref name=":0" /> 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. <ref name=":2">Barik, S.K., Biswal, M.P. & Chakravarty, D. Two-stage stochastic programming problems involving interval discrete random variables. OPSEARCH 49, 280–298 (2012). ~~<nowiki>https://doi.org/10.1007/s12597-012-0078-1</nowiki>~~</ref> Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling. <ref name=":0" />		Modeling through stochastic programming is often adopted because of its proactive-reactive decision-making feature to address uncertainty. <ref name=":3"> Chu, Yunfei, and Fengqi You. [https://doi.org/10.1021/ie402621t “Integration of Scheduling and Dynamic Optimization of Batch Processes under Uncertainty: Two-Stage Stochastic Programming Approach and Enhanced Generalized Benders Decomposition Algorithm.”] ''Industrial & Engineering Chemistry Research'', vol. 52, no. 47, 2013, pp. 16851–16869.</ref> 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. <ref name=":0" /> 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. <ref name=":3" /> 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. <ref name=":3" /> 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. <ref name=":4">Barik, S.K., Biswal, M.P. & Chakravarty, D. [https://doi.org/10.1007/s12597-012-0078-1 "Two-stage stochastic programming problems involving interval discrete random variables."] ''OPSEARCH'' 49, 280–298 (2012).</ref> Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling. <ref name=":3" />

	=== Methodology ===		=== Methodology ===

Hangyu: /* Theory, methodology, and/or algorithmic discussion */

2021-12-16T04:28:49Z

Theory, methodology, and/or algorithmic discussion

← Older revision		Revision as of 00:28, 16 December 2021
Line 10:		Line 10:
	== Theory, methodology, and/or algorithmic discussion ==		== Theory, methodology, and/or algorithmic discussion ==

	Modeling through stochastic programming is often adopted because of its proactive-reactive decision-making feature to address uncertainty. <ref name=":0" /> 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. <ref name=":1" /> 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. <ref name=":0" /> 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. <ref name=":0" /> 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. <ref name=":2">Barik, S.K., Biswal, M.P. & Chakravarty, D. Two-stage stochastic programming problems involving interval discrete random variables. OPSEARCH 49, 280–298 (2012). <nowiki>https://doi.org/10.1007/s12597-012-0078-1</nowiki></ref> Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling. <ref name=":0" />		Modeling through stochastic programming is often adopted because of its proactive-reactive decision-making feature to address uncertainty. <ref name=":3"> Chu, Yunfei, and Fengqi You. [https://doi.org/10.1021/ie402621t “Integration of Scheduling and Dynamic Optimization of Batch Processes under Uncertainty: Two-Stage Stochastic Programming Approach and Enhanced Generalized Benders Decomposition Algorithm.”] ''Industrial & Engineering Chemistry Research'', vol. 52, no. 47, 2013, pp. 16851–16869.</ref> 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. <ref name=":1" /> 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. <ref name=":0" /> 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. <ref name=":0" /> 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. <ref name=":2">Barik, S.K., Biswal, M.P. & Chakravarty, D. Two-stage stochastic programming problems involving interval discrete random variables. OPSEARCH 49, 280–298 (2012). <nowiki>https://doi.org/10.1007/s12597-012-0078-1</nowiki></ref> Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling. <ref name=":0" />

	=== Methodology ===		=== Methodology ===

Hangyu: /* Theory, methodology, and/or algorithmic discussion */

2021-12-16T04:24:50Z

Theory, methodology, and/or algorithmic discussion

← Older revision		Revision as of 00:24, 16 December 2021
Line 9:		Line 9:

	== Theory, methodology, and/or algorithmic discussion ==		== 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. <ref name=":0" /> 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. <ref name=":1" /> 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. <ref name=":0" /> 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. <ref name=":0" /> 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. <ref name=":2">Barik, S.K., Biswal, M.P. & Chakravarty, D. Two-stage stochastic programming problems involving interval discrete random variables. OPSEARCH 49, 280–298 (2012). <nowiki>https://doi.org/10.1007/s12597-012-0078-1</nowiki></ref> Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling. <ref name=":0" />		Modeling through stochastic programming is often adopted because of its proactive-reactive decision-making feature to address uncertainty. <ref name=":0" /> 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. <ref name=":1" /> 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. <ref name=":0" /> 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. <ref name=":0" /> 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. <ref name=":2">Barik, S.K., Biswal, M.P. & Chakravarty, D. Two-stage stochastic programming problems involving interval discrete random variables. OPSEARCH 49, 280–298 (2012). <nowiki>https://doi.org/10.1007/s12597-012-0078-1</nowiki></ref> Two-stage stochastic programming is suited for problems with a hierarchical structure, such as integrated process design, and planning and scheduling. <ref name=":0" />

Hangyu: /* Introduction */

2021-12-16T04:23:22Z

Introduction

@@ Line 2: / Line 2: @@
 == Introduction ==
-[[File:Screen Shot 2021-11-28 at 10.02.36 AM.png|thumb|557x557px|Two-stage stochastic programming scheme: conceptual representation is on the left; scenario tree is on the right, where <math>x</math> denotes the first stage decisions, <math>y_{\omega}</math> denotes the second stage decisions for each scenario <math>\omega</math>. <math>\tau_{\omega}, h_{\omega}</math> denotes the probability and the constraints of each scenario, respectively. <ref name=":11">Li, C., & Grossmann, I. E. (2021). A review of stochastic programming methods for optimization of process systems under uncertainty. Frontiers in Chemical Engineering, 2. https://doi.org/10.3389/fceng.2020.622241 </ref>]]
+[[File:Screen Shot 2021-11-28 at 10.02.36 AM.png|thumb|557x557px|Two-stage stochastic programming scheme: conceptual representation is on the left; scenario tree is on the right, where <math>x</math> denotes the first stage decisions, <math>y_{\omega}</math> denotes the second stage decisions for each scenario <math>\omega</math>. <math>\tau_{\omega}, h_{\omega}</math> denotes the probability and the constraints of each scenario, respectively. <ref name=":0">Li Can, Grossmann Ignacio E. [https://doi.org/10.3389/fceng.2020.622241 “A Review of Stochastic Programming Methods for Optimization of Process Systems Under Uncertainty,”] ''Frontiers in Chemical Engineering'' 2021, Vol. 2</ref>]]
-Stochastic Programming is a mathematical framework to help decision-making under uncertainty. <ref name=":1">Li Can, Grossmann Ignacio E., “A Review of Stochastic Programming Methods for Optimization of Process Systems Under Uncertainty,” Frontiers in Chemical Engineering 2021, Vol. 2; DOI: 10.3389/fceng.2020.622241</ref> Deterministic optimization frameworks like the linear program (LP), nonlinear program (NLP), mixed-integer program (MILP), or mixed-integer nonlinear program (MINLP) are well-studied, playing a vital role in solving all kinds of optimization problems. But this sort of formulation assumes that one has perfect knowledge of the future outcome of the system, and the entire system is deterministic. (Lshape page) They tend to produce sub-optimal results in some real-world situations where uncertainties significantly impact the system behavior. To address this problem, stochastic programming extends the deterministic optimization methodology by introducing random variables that model the uncertain nature of real-world problems, trying to hedge against risks and find the optimal decision with the best-expected performance under all possible situations. With uncertainties being widespread, this general stochastic framework finds applications in a broad spectrum of problems across sectors, from electricity generation, financial planning, supply chain management to process systems engineering, mitigation of climate change, and pollution control, and many others. <ref name=":1" />
+Stochastic Programming is a mathematical framework to help decision-making under uncertainty. <ref name=":0" /> Deterministic optimization frameworks like the linear program (LP), nonlinear program (NLP), mixed-integer program (MILP), or mixed-integer nonlinear program (MINLP) are well-studied, playing a vital role in solving all kinds of optimization problems. But this sort of formulation assumes that one has perfect knowledge of the future outcome of the system, and the entire system is deterministic. <ref name=":1">J. Schif [https://www.eecs.tufts.edu/~aloupis/comp150/projects/Jeremy-S/2sLP-Report.pdf "The L Shaped Algorithm"]</ref> They tend to produce sub-optimal results in some real-world situations where uncertainties significantly impact the system behavior. To address this problem, stochastic programming extends the deterministic optimization methodology by introducing random variables that model the uncertain nature of real-world problems, trying to hedge against risks and find the optimal decision with the best-expected performance under all possible situations. With uncertainties being widespread, this general stochastic framework finds applications in a broad spectrum of problems across sectors, from electricity generation, financial planning, supply chain management to process systems engineering, mitigation of climate change, and pollution control, and many others. <ref name=":0" />
-Since its origin in the 1950s, the stochastic programming framework has been studied extensively. [Dantizig, 1955] A significant number of theoretical and algorithmic developments have been made to tackle uncertainty under different situations. To make an in-depth and fruitful investigation, we limited our topic to two-stage stochastic programming, the simplest form that focuses on situations with only one decision-making step. We will examine the most popular algorithm for solving such programs and discuss other aspects of this fascinating optimization framework.
+Since its origin in the 1950s, the stochastic programming framework has been studied extensively. <ref name=":2">Dantzig, George B. [https://doi.org/10.1287/mnsc.1.3-4.197 “Linear Programming under Uncertainty.”] ''Management Science'', vol. 1, no. 3-4, 1955, pp. 197–206. </ref> A significant number of theoretical and algorithmic developments have been made to tackle uncertainty under different situations. To make an in-depth and fruitful investigation, we limited our topic to two-stage stochastic programming, the simplest form that focuses on situations with only one decision-making step. We will examine the most popular algorithm for solving such programs and discuss other aspects of this fascinating optimization framework.
 == Theory, methodology, and/or algorithmic discussion ==

Hangyu: /* Introduction */

2021-12-16T04:05:40Z

Introduction

@@ Line 3: / Line 3: @@
 == Introduction ==
 [[File:Screen Shot 2021-11-28 at 10.02.36 AM.png|thumb|557x557px|Two-stage stochastic programming scheme: conceptual representation is on the left; scenario tree is on the right, where <math>x</math> denotes the first stage decisions, <math>y_{\omega}</math> denotes the second stage decisions for each scenario <math>\omega</math>. <math>\tau_{\omega}, h_{\omega}</math> denotes the probability and the constraints of each scenario, respectively. <ref name=":11">Li, C., & Grossmann, I. E. (2021). A review of stochastic programming methods for optimization of process systems under uncertainty. Frontiers in Chemical Engineering, 2. https://doi.org/10.3389/fceng.2020.622241 </ref>]]
 Stochastic Programming, also referred to as Stochastic Optimization, is a mathematical framework to help decision-making processes under uncertainty. <ref name=":0"> “Integration of Scheduling and Dynamic Optimization of Batch Processes under Uncertainty: Two-Stage Stochastic Programming Approach and Enhanced Generalized Benders Decomposition Algorithm,”Yunfei Chu and Fengqi You, Industrial & Engineering Chemistry Research 2013 52 (47), 16851-16869 DOI: 10.1021/ie402621t </ref> With uncertainties being widespread, Stochastic Programming is a risk-neutral mathematical framework that finds application in areas, such as process systems engineering. <ref name=":1">Li Can, Grossmann Ignacio E., “A Review of Stochastic Programming Methods for Optimization of Process Systems Under Uncertainty,” Frontiers in Chemical Engineering 2021, Vol. 2; DOI: 10.3389/fceng.2020.622241
 </ref> 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 the process of raw materials, availability of raw materials, price of different products, operation time and cost, and order demands are considered without factoring in uncertainty. However, such assumptions are not realistic because uncertainty doesn’t come with forewarning. Hence, uncertainty needs to be factored in always. <ref name=":3">“A Tutorial on Stochastic Programming,” Shapiro, Alexander and Philpott, Andy</ref>

Hangyu: /* Numerical Example */

2021-12-16T03:09:20Z

Numerical Example

@@ Line 170: / Line 170: @@
 ''' Iteration 2:'''
-<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta | x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2\}</math>. Result is <math>z = -22.992, x^2 = (4, 8)^T, \theta ^2 = -182.992</math>.
+<em>Step 1.</em> The master program is
 <em>Step 2.</em> No feasibility cut is needed.
@@ Line 196: / Line 205: @@
 ''' Iteration 3:'''
-<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta | x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84\}</math>. Result is <math>z = -10.39375, x^3 = (6.6828, 5.3172)^T, \theta ^3 = -156.97994</math>.
+<em>Step 1.</em> The master program is
 <em>Step 2.</em> No feasibility cut is needed.
@@ Line 222: / Line 240: @@
 ''' Iteration 4:'''
-<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta | x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84, 11.52x_1 + 9.6x_2 + \theta \ge -21.04\}</math>. Result is <math>z = -8.895, x^4 = (4, 3.375)^T, \theta ^4 = -99.52</math>.
+<em>Step 1.</em> The master program is
 <em>Step 2.</em> No feasibility cut is needed.
@@ Line 246: / Line 274: @@
 ''' Iteration 5:'''
-<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta | x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84, 11.52x_1 + 9.6x_2 + \theta \ge -21.04, 13.344x_1 + 13.056x_2 + \theta \ge 0\}</math>. Result is <math>z = -8.5583, x^5 = (4.6667, 3.625)^T, \theta ^5 = -109.6</math>.
+<em>Step 1.</em> The master program is
 <em>Step 2.</em> No feasibility cut is needed.

Hangyu: /* Numerical Example */

2021-12-16T02:56:36Z

Numerical Example

← Older revision		Revision as of 22:56, 15 December 2021
Line 140:		Line 140:
	We should note that in this case, as <math>x \ge 0</math>, <math>d \ge 0</math> and <math>y_1, y_2 \ge 0</math>, the second stage is always feasible, which means <math> x \in K_2</math> always hold true. So we could skip the feasibility cuts (step 2) in all iterations. The <em>L</em>-shaped method iterations are shown below:		We should note that in this case, as <math>x \ge 0</math>, <math>d \ge 0</math> and <math>y_1, y_2 \ge 0</math>, the second stage is always feasible, which means <math> x \in K_2</math> always hold true. So we could skip the feasibility cuts (step 2) in all iterations. The <em>L</em>-shaped method iterations are shown below:

	''' Iteration 1:'''
			''' Iteration 1:'''

	<em>Step 1.</em> With no <math>\theta </math>, the master program is <math>z = min\{10x_1 + 15x_2 \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2\}</math>. Result is <math>x^1 = (4, 2)^T</math>. Set <math>\theta ^1 = -\infty </math>.		<em>Step 1.</em> With no <math>\theta </math>, the master program is <math>z = min\{10x_1 + 15x_2 \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2\}</math>. Result is <math>x^1 = (4, 2)^T</math>. Set <math>\theta ^1 = -\infty </math>.
Line 165:		Line 166:
	: Thus, <math>w^1 = -5.2 - (8.352, 18.048) \cdot x^1 = -74.704 > \theta ^1 = -\infty </math>, we add the cut		: Thus, <math>w^1 = -5.2 - (8.352, 18.048) \cdot x^1 = -74.704 > \theta ^1 = -\infty </math>, we add the cut
	:<math>8.352x_1 + 18.048x_2 + \theta \ge -5.2</math>		:<math>8.352x_1 + 18.048x_2 + \theta \ge -5.2</math>


	''' Iteration 2:'''		''' Iteration 2:'''

	<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2\}</math>. Result is <math>z = -22.992, x^2 = (4, 8)^T, \theta ^2 = -182.992</math>.		<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2\}</math>. Result is <math>z = -22.992, x^2 = (4, 8)^T, \theta ^2 = -182.992</math>.

Line 192:		Line 195:

	''' Iteration 3:'''		''' Iteration 3:'''

	<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84\}</math>. Result is <math>z = -10.39375, x^3 = (6.6828, 5.3172)^T, \theta ^3 = -156.97994</math>.		<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84\}</math>. Result is <math>z = -10.39375, x^3 = (6.6828, 5.3172)^T, \theta ^3 = -156.97994</math>.

Line 217:		Line 221:

	''' Iteration 4:'''		''' Iteration 4:'''

	<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84, 11.52x_1 + 9.6x_2 + \theta \ge -21.04\}</math>. Result is <math>z = -8.895, x^4 = (4, 3.375)^T, \theta ^4 = -99.52</math>.		<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84, 11.52x_1 + 9.6x_2 + \theta \ge -21.04\}</math>. Result is <math>z = -8.895, x^4 = (4, 3.375)^T, \theta ^4 = -99.52</math>.

Line 240:		Line 245:

	''' Iteration 5:'''		''' Iteration 5:'''

	<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84, 11.52x_1 + 9.6x_2 + \theta \ge -21.04, 13.344x_1 + 13.056x_2 + \theta \ge 0\}</math>. Result is <math>z = -8.5583, x^5 = (4.6667, 3.625)^T, \theta ^5 = -109.6</math>.		<em>Step 1.</em> The master program is <math>z = min\{10x_1 + 15x_2 + \theta \| x_1 + x_2 \le 12, x_1 \ge 4, x_2 \ge 2, 8.352x_1 + 18.048x_2 + \theta \ge -5.2, 21.12x_1 + \theta \ge -15.84, 11.52x_1 + 9.6x_2 + \theta \ge -21.04, 13.344x_1 + 13.056x_2 + \theta \ge 0\}</math>. Result is <math>z = -8.5583, x^5 = (4.6667, 3.625)^T, \theta ^5 = -109.6</math>.