Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Pro...
详细信息
Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Program A 106(3):423-432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is governed by independent uniform distributions. We show that Dyer and Stougie's proof is not correct, and we offer a correction which establishes the stronger result that even the approximate solution of such problems is #P-hard for a sufficiently high accuracy. We also provide new results which indicate that linear two-stage stochastic programs with random recourse seem even more challenging to solve.
作者：
Hou, ZeyuLu, WenxiJilin Univ
Key Lab Groundwater Resources & Environm Minist Educ Changchun 130021 Jilin Peoples R China Jilin Univ
Coll Environm & Resources Changchun 130021 Jilin Peoples R China
Surrogate-based simulation-optimization techniques are widely applied in developing optimal remediation strategies that increase the efficiency and reduce the cost of surfactant-enhanced aquifer remediation (SEAR) whe...
详细信息
Surrogate-based simulation-optimization techniques are widely applied in developing optimal remediation strategies that increase the efficiency and reduce the cost of surfactant-enhanced aquifer remediation (SEAR) when clearing dense nonaqueous phase liquids (DNAPLs). In such processes, there are many uncertainty factors that may greatly affect the optimization outcome of a SEAR strategy selection. However, previous research on this subject rarely incorporates an uncertainty analysis. This paper presents an uncertainty analysis of both the simulation model and the ensemble surrogate model used to optimize SEAR strategies. Set pair analysis (SPA) and kriging methods were used to build the ensemble surrogate model. The probability distributions of the residuals of the outputs between the ensemble surrogate model and the simulation model, run on 100 testing samples, were analyzed to ascertain the uncertainty of the surrogate model, which was found to be less than 1.5%. The uncertainty of the simulation model was derived by combining a Monte Carlo random simulation with the Sobol' global sensitivity analysis. Finally, a stochastic nonlinear programming model was established to compute the optimal remediation strategies for the remediation target under different confidence levels. This research will allow decision makers to more confidently select the optimal remediation strategy for a given scenario by balancing the reliability of model prediction with the cost of the remediation strategy according to the demands of the project.
Some disasters such as earthquakes, floods and hurricanes may result in evacuation for people in an affected area. This paper focuses on finding the a priori evacuation plans by considering side constraints and scenar...
详细信息
Some disasters such as earthquakes, floods and hurricanes may result in evacuation for people in an affected area. This paper focuses on finding the a priori evacuation plans by considering side constraints and scenario-based stochastic link travel times and capacities. Hence a stochastic programming framework is developed so as to provide a reorganization of the traffic routing for a disaster response. Considering the different preferences of decision-makers, three evaluation criteria are introduced to formulate the objective function. Crisp linear equivalents for different evacuation strategies are further deduced to simplify solution methodologies. A heuristic algorithm combining the Lagrangian relaxation-based approach with K-shortest path techniques is designed to solve the expected disutility model. The experimental results indicate that the algorithm can solve large-scale instances for the problem of interest efficiently and effectively. (C) 2016 Elsevier Ltd. All rights reserved.
We consider multistage stochastic programs, in which decisions can adapt over time, (i.e., at each stage), in response to observation of one or more random variables (uncertain parameters). The case that the time at w...
详细信息
We consider multistage stochastic programs, in which decisions can adapt over time, (i.e., at each stage), in response to observation of one or more random variables (uncertain parameters). The case that the time at which each observation occurs is decision-dependent, known as stochastic programming with endogeneous observation of uncertainty, presents particular challenges in handling non-anticipativity. Although such stochastic programs can be tackled by using binary variables to model the time at which each endogenous uncertain parameter is observed, the consequent conditional non-anticipativity constraints form a very large class, with cardinality in the order of the square of the number of scenarios. However, depending on the properties of the set of scenarios considered, only very few of these constraints may be required for validity of the model. Here we characterize minimal sufficient sets of non-anticipativity constraints, and prove that their matroid structure enables sets of minimum cardinality to be found efficiently, under general conditions on the structure of the scenario set.
This paper addresses dynamic cell formation problem (DCFP) which has been explored vastly for several years. Although a considerable body of literature in this filed, two remarkable aspects have been significantly ign...
详细信息
This paper addresses dynamic cell formation problem (DCFP) which has been explored vastly for several years. Although a considerable body of literature in this filed, two remarkable aspects have been significantly ignored so far, as uncertainty and human-related issues. In order to compensate such a shortage, this paper develops a bi-objective stochastic model. The first objective function of the developed model seeks to minimize total cost of machine procurement, machine relocation, inter-cell moves, overtime utilization, worker hiring/laying-off, and worker moves between cells;while the second objective function maximizes labor utilization of the cellular manufacturing system. In the developed model, labor utilization, worker overtime cost, worker hiring/laying off, and worker cell assignment are considered to tackle some of the most notable human-related issues in DCFP. Considering the complexity of the proposed model, a hybrid Tabu Search-Genetic Algorithm (TS-GA) is proposed whose strength is validated to obtain optimal and near optimal solutions through conducted experimental results. (C) 2016 Elsevier Ltd. All rights reserved.
In this study, a risk-based interactive multi-stage stochastic programming (RIMSP) approach is proposed through incorporating the fractile criterion method and chance-constrained programming within a multistage decisi...
详细信息
In this study, a risk-based interactive multi-stage stochastic programming (RIMSP) approach is proposed through incorporating the fractile criterion method and chance-constrained programming within a multistage decision-making framework. RIMSP is able to deal with dual uncertainties expressed as random boundary intervals that exist in the objective function and constraints. Moreover, RIMSP is capable of reflecting dynamics of uncertainties, as well as the trade-off between the total net benefit and the associated risk. A water allocation problem is used to illustrate applicability of the proposed methodology. A set of decision alternatives with different combinations of risk levels applied to the objective function and constraints can be generated for planning the water resources allocation system. The results can help decision makers examine potential interactions between risks related to the stochastic objective function and constraints. Furthermore, a number of solutions can be obtained under different water policy scenarios, which are useful for decision makers to formulate an appropriate policy under uncertainty. The performance of RIMSP is analyzed and compared with an inexact multi-stage stochastic programming (IMSP) method. Results of comparison experiment indicate that RIMSP is able to provide more robust water management alternatives with less system risks in comparison with IMSP. (C) 2016 Elsevier Ltd. All rights reserved.
The introduction of non-conventional energy sources (NCES) to industrial processes is a viable alternative to reducing the energy consumed from the grid. However, a robust coordination of the local energy resources wi...
详细信息
The introduction of non-conventional energy sources (NCES) to industrial processes is a viable alternative to reducing the energy consumed from the grid. However, a robust coordination of the local energy resources with the power imported from the distribution grid is still an open issue, especially in countries that do not allow selling energy surpluses to the main grid. In this paper, we propose a stochastic-programming-based energy management system (EMS) focused on self-consumption that provides robustness to both sudden NCES or load variations, while preventing power injection to the main grid. The approach is based on a finite number of scenarios that combines a deterministic structure based on spectral analysis and a stochastic model that represents variability. The parameters to generate these scenarios are updated when new information arrives. We tested the proposed approach with data from a copper extraction mining process. It was compared to a traditional EMS with perfect prediction, i.e., a best case scenario. Test results show that the proposed EMS is comparable to the EMS with perfect prediction in terms of energy imported from the grid (slightly higher), but with less power changes in the distribution side and enhanced dynamic response to transients of wind power and load. This improvement is achieved with a non-significant computational time overload.
Hedging of an option book in an incomplete market with transaction costs is an important problem in finance that many banks have to solve on a daily basis. In this paper, we develop a stochastic programming (SP) model...
详细信息
Hedging of an option book in an incomplete market with transaction costs is an important problem in finance that many banks have to solve on a daily basis. In this paper, we develop a stochastic programming (SP) model for the hedging problem in a realistic setting, where all transactions take place at observed bid and ask prices. The SP model relies on a realistic modeling of the important risk factors for the application, the price of the underlying security and the volatility surface. The volatility surface is unobservable and must be estimated from a cross section of observed option quotes that contain noise and possibly arbitrage. In order to produce arbitrage-free volatility surfaces of high quality as input to the SP model, a novel non-parametric estimation method is used. The dimension of the volatility surface is infinite and in order to be able solve the problem numerically, we use discretization and principal component analysis to reduce the dimensions of the problem. Testing the model out-of-sample for options on the Swedish OMXS30 index, we show that the SP model is able to produce a hedge that has both a lower realized risk and cost compared with dynamic delta and delta-vega hedging strategies.
The paper suggests a possible cooperation between stochastic programming and optimal control for the solution of multistage stochastic optimization problems. We propose a decomposition approach for a class of multista...
详细信息
The paper suggests a possible cooperation between stochastic programming and optimal control for the solution of multistage stochastic optimization problems. We propose a decomposition approach for a class of multistage stochastic programming problems in arborescent form (i.e. formulated with implicit non-anticipativity constraints on a scenario tree). The objective function of the problem can be either linear or nonlinear, while we require that the constraints are linear and involve only variables from two adjacent periods (current and lag 1). The approach is built on the following steps. First, reformulate the stochastic programming problem into an optimal control one. Second, apply a discrete version of Pontryagin maximum principle to obtain optimality conditions. Third, discuss and rearrange these conditions to obtain a decomposition that acts both at a time stage level and at a nodal level. To obtain the solution of the original problem we aggregate the solutions of subproblems through an enhanced mean valued fixed point iterative scheme.
We consider expected return, Conditional Value at Risk, and liquidity criteria in a multi-period portfolio optimization setting modeled by stochastic programming. We aim to identify a preferred solution of the decisio...
详细信息
We consider expected return, Conditional Value at Risk, and liquidity criteria in a multi-period portfolio optimization setting modeled by stochastic programming. We aim to identify a preferred solution of the decision maker (DM) by obtaining information on her/his preferences. We use a weighted Tchebycheff program to generate representative sets of solutions. Our approach models the stochasticity of market movements by stochastic programming. Working with multiple scenario trees, we construct confidence ellipsoids around representative solutions, and present them to the DM for her/him to make a choice. With each iteration of the approach, an increasingly concentrated set of ellipsoids around the DM's choices are generated. The procedure is demonstrated with tests performed using stocks traded on Borsa Istanbul.
暂无评论