Stochastic optimization
Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations. Traditionally, the main focus in stochastic optimization has been various stochastic mathematical programming (such as linear programming, convex programming). In recent years, there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science community. In this article, we survey some of the recent results on various stochastic versions of classical combinatorial optimization problems. Since most problems in this domain are NP-hard (or #P-hard, or even PSPACE-hard), we focus on the results which provide polynomial time approximation algorithms with provable approximation guarantees. Our discussions are centered around a few representative problems, such as stochastic knapsack, stochastic matching, multi-armed bandit etc. We use these examples to introduce several popular stochastic models, such as the fixed-set model, 2-stage stochastic optimization model, stochastic adaptive probing model etc, as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems, including the linear programming relaxation approach, boosted sampling, content resolution schemes, Poisson approximation etc.We also provide some open research questions along the way. Our purpose is to provide readers a quick glimpse to the models, problems, and techniques in this area, and hopefully inspire new contributions .
This paper analyzes the multi-choice stochastic transportation problem where the cost coefficients of the objective function and the demand parameters of the constraints follow multi-choice parameters. Assume that the supply parameters of the constraints in a transportation problem (TP) follow logistic distribution. The main objective of this paper is to select an appropriate choice from the multi-choices for the cost coefficients of the objective function and the demand of the constraints in the TP by introducing Lagrange’s interpolating polynomial in such a way that the total cost is minimized and satisfies the required demand. Using stochastic programming, the stochastic supply constraints of the TP are transformed into deterministic constraints. Finally, a non-linear deterministic model is formulated. Using Lingo software, the optimal solution of the proposed problem is derived. To illustrate the methodology, a real-life problem on the TP is considered.
This paper studies a system consisting of two parallel queues with transfers of customers. In the system, one queue is called main queue and the other one is called auxiliary queue. The main queue is monitored at exponential time instances. At a monitoring instant, if the number of customers in main queue reaches L (> K), a batch of L−K customers is transferred from the main queue to the auxiliary queue, and if the number of customers in main queue is less than or equal to K, the transfers will not happen. For this system, by using a Foster-Lyapunov type condition, we establish a sufficient stability condition. Then, we provide a sufficient condition under which,for any fixed number of customers in the auxiliary queue, the stationary probability of the number of customers in the main queue has an exact geometric tail asymptotic as the number of customers in main queue increases to infinity. Finally, we give some numerical results to illustrate the impact of some critical model parameters on the decay rate.
Bulk arrival retrial G-queue with impatient customers and multi-services subject to server breakdowns has been analyzed. The system allows the arrival of two types of customers: positive customers and negative customers in the system. The negative customers make the server fail if they find the server in busy state, whereas positive customers are served if the server is idle otherwise they join the virtual pool of customers called orbit. The customers from the retrial orbit try their chance again for the service. The customers have the option of obtaining more than one service. Moreover, the customers are impatient and may renege from the system with probability (1−r ). The server is sent for repair as soon as it breakdowns; after repair, the service process starts again. Also, the server has the provision to initiate the service when there areN customers accumulated in the system. Using supplementary variables technique and generating functions, various performance measures like reliability indices and long run probabilities have been obtained.
When executing a large order of stocks in a market, one important factor in forming the optimal trading strategy is to consider the price impact of large-volume trading activity. Minimizing a risk measure of the implementation shortfall, i.e., the difference between the value of a trader’s initial equity position and the sum of cash flow he receives from his trading process, is essentially a stochastic control problem. In this study, we investigate such a practical problem under a dynamic coherent risk measure in a market in which the stock price dynamics has a feature of momentum effect. We develop a fast approximation solution scheme, which is critical in highfrequency trading. We demonstrate some prominent features of our derived solution algorithm in providing useful guidance for real implementation.
Joint probability function refers to the probability function that requires multiple conditions to satisfy simultaneously. It appears naturally in chanceconstrained programs. In this paper, we derive closed-form expressions of the gradient and Hessian of joint probability functions and develop Monte Carlo estimators of them. We then design a Monte Carlo algorithm, based on these estimators, to solve chance-constrained programs. Our numerical study shows that the algorithm works well, especially only with the gradient estimators.
In this paper, we present a unified framework for decision making under uncertainty. Our framework is based on the composite of two risk measures, where the inner risk measure accounts for the risk of decision if the exact distribution of uncertain model parameters were given, and the outer risk measure quantifies the risk that occurs when estimating the parameters of distribution. We show that the model is tractable under mild conditions. The framework is a generalization of several existing models, including stochastic programming, robust optimization, distributionally robust optimization. Using this framework, we study a few new models which imply probabilistic guarantees for solutions and yield less conservative results compared to traditional models. Numerical experiments are performed on portfolio selection problems to demonstrate the strength of our models.
