This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overb...
详细信息
ISBN:
(纸本)3540343067
This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overbooking are examples of such online stochastic reservations. The paper studies how to adapt the online stochastic framework and the consensus and regret algorithms proposed earlier to online stochastic reservation systems. On the theoretical side, it presents a constant sub-optimality approximation of multi-knapsack problems, leading to a regret algorithm that evaluates each scenario with a single mathematical programming optimization followed by a small number of dynamic programs for one-dimensional knapsacks. On the experimental side, the paper demonstrates the effectiveness of the regret algorithm on multi-knapsack problems (with and without overloading) based on the benchmarks proposed earlier.
We consider optimization problems for minimizing conditional valueat-risk (CVaR) from a computational point of view, with an emphasis on financial applications. As a general solution approach, we suggest to reformulat...
详细信息
We consider optimization problems for minimizing conditional valueat-risk (CVaR) from a computational point of view, with an emphasis on financial applications. As a general solution approach, we suggest to reformulate these CVaR optimization problems as two-stage recourse problems of stochastic programming. Specializing the L-shaped method leads to a new algorithm for minimizing conditional value-at-risk. We implemented the algorithm as the solver CVaRMin. For illustrating the performance of this algorithm, we present some comparative computational results with two kinds of test problems. Firstly, we consider portfolio optimization problems with 5 random variables. Such problems involving conditional value at risk play an important role in financial risk management. Therefore, besides testing the performance of the proposed algorithm, we also present computational results of interest in finance. Secondly, with the explicit aim of testing algorithm performance, we also present comparative computational results with randomly generated test problems involving 50 random variables. In all our tests, the experimental solver, based on the new approach, outperformed by at least one order of magnitude all general-purpose solvers, with an accuracy of solution being in the same range as that with the LP solvers.
This paper addresses the location problem of distribution centers (DC) in a distribution network with unreliable suppliers and random demand. A two-period model is proposed in which selected suppliers are available in...
详细信息
ISBN:
(纸本)9781424403103
This paper addresses the location problem of distribution centers (DC) in a distribution network with unreliable suppliers and random demand. A two-period model is proposed in which selected suppliers are available in the first period and can fail in the second period. The facility location/supplier reliability problem is formulated as a stochastic programming problem for minimizing total fixed facility costs, transportation costs, DC replenishment costs, DC inventory and safety stock costs. Since the problem is NP-hard non linear stochastic optimization problem, we propose a Monte Carlo optimization approach combining the sample average approximation (SAA) scheme and an efficient heuristic based on Lagrangian relaxation approach for solving the related sample optimization problem. Computational results are provided to assess the efficiency of the proposed method.
A unit commitment problem has long been known in the class of short-term functions and decisions, inherited from vertically integrated utility. In the competitive environment, the problem has become more complicated d...
详细信息
ISBN:
(纸本)9781424402274
A unit commitment problem has long been known in the class of short-term functions and decisions, inherited from vertically integrated utility. In the competitive environment, the problem has become more complicated due to the fact that any action taken will now influence profitability of decision maker such as generation companies, load serving entities, and so forth. Thus, not only do economic agents face operational risks, but they also need to procure their operations against financial risks front volatility in fuel, contract, and electricity prices. This leads to the evolution of stochastic unit commitment in this paper integrating risk management tools, i.e., electricity derivatives, so as to reduce the impacts from both operational and financial risks in the short run. The planning model is structured of stochastic mixed-integer program with recourse cost. A case study will be addressed with preliminary result presenting an improved solution.
This paper addresses the elective surgery planning problem when the operating rooms' capacity is shared between elective and emergency patients. The planning problem consists in determining the set of elective pat...
详细信息
ISBN:
(纸本)9781424403103
This paper addresses the elective surgery planning problem when the operating rooms' capacity is shared between elective and emergency patients. The planning problem consists in determining the set of elective patients that would be operated in each period over a planning horizon in order to minimize patients related costs and overtime costs of operating rooms. A stochastic integer programming model is proposed. Lagrangian relaxation is used to decompose the planning problem into period-level sub-problems that are solved by a dynamic programming method. The dual problem is solved iteratively using a sub-gradient algorithm. Feasible plans are derived from relaxed solutions using a heuristic and improved with a "local search heuristic". This approach results in both near-optimal solution and a lower bound to assess the degree of optimality. Numerical experimentations show that solutions within 1% of the optimum are obtained in a short computation time for problems of practical sizes.
Electricity suppliers are always confronted with demand uncertainty even though the state-of-the-art forecast and sophisticated control systems are employed to ensure both security and reliability. With the emergence ...
详细信息
ISBN:
(纸本)9789171785855
Electricity suppliers are always confronted with demand uncertainty even though the state-of-the-art forecast and sophisticated control systems are employed to ensure both security and reliability. With the emergence of power market, the market participants such as generation companies, load serving entities, etc., even face higher degree of uncertainty in its operation planning. This is due to the unique characteristics of electricity which could result in unprecedented price spikes. A portfolio of supply contracts including forwards and options is a set of tools for reducing the impacts of both demand uncertainty and price volatility by increasing production flexibility. Thus, a procurement strategy can be implemented by providing more choices via contracting in addition to self generation and spot market transactions. In this framework, a two-stage planning model is developed for improving the short-term operation by incorporating risk hedging strategy in the planning problem so as to meet stochastic demand.
We introduce a modelling paradigm which integrates credit risk and market risk in describing the random dynamical behaviour of the underlying fixed income assets. We then consider an asset and liability management (AL...
详细信息
We introduce a modelling paradigm which integrates credit risk and market risk in describing the random dynamical behaviour of the underlying fixed income assets. We then consider an asset and liability management (ALM) problem and develop a multistage stochastic programming model which focuses on optimum risk decisions. These models exploit the dynamical multiperiod structure of credit risk and provide insight into the corrective recourse decisions whereby issues such as the timing risk of default is appropriately taken into consideration. We also present an index tracking model in which risk is measured (and optimised) by the CVaR of the tracking portfolio in relation to the index. In-sample as well as out-of-sample (backtesting) experiments are undertaken to validate our approach. The main benefits of backtesting, that is, ex-post analysis are that (a) we gain insight into asset allocation decisions, and (b) we are able to demonstrate the feasibility and flexibility of the chosen framework. (c) 2005 Published by Elsevier B.V.
The possibility of controlling risk in stochastic power optimization by incorporating special risk functionals, so-called polyhedral risk measures, into the objective is demonstrated. We present an exemplary optimizat...
详细信息
ISBN:
(纸本)9789171785855
The possibility of controlling risk in stochastic power optimization by incorporating special risk functionals, so-called polyhedral risk measures, into the objective is demonstrated. We present an exemplary optimization model for mean-risk optimization of an electricity portfolios of a price-taking retailer. stochasticity enters the model via uncertain electricity demand, heat demand, spot prices, and future prices. The objective is to maximize the expected overall revenue and, simultaneously, to minimize risk in terms of multiperiod risk measures, i.e., risk measures that take into account intermediate cash values in order to avoid liquidity problems at any time. We compare the effect of different multiperiod polyhedral risk measures that had been suggested in our earlier work.
The paper investigates the features of separately clearing the energy in the day-ahead market and then doing the same for the real-time market from the system operator's perspective. The analysis will show that th...
详细信息
ISBN:
(纸本)9781424401772
The paper investigates the features of separately clearing the energy in the day-ahead market and then doing the same for the real-time market from the system operator's perspective. The analysis will show that this separate clearing mechanism is not always the most economical. An alternative approach based on co-optimization of both energy markets is presented. Considering stochastic electric demand, a novel integrated energy dispatching model (IEDM) is proposed for system operators that schedules day-ahead energy trading taking possible real-time demand and prices into account to find an optimal day-ahead dispatching scheme so as to achieve the total purchase cost minimum. Mathematical analysis is provided to illustrate the IEDM is more economical than the conventional separate dispatching approach. The IEDM solution integrates Monte Carlo simulation and linear programming with Hooke and Jeeves pattern search method. A 6-unit system example is applied to illustrate that the IEDM provides a more economical approach.
We introduce and study the following model for routing uncertain demands through a network. We are given a capacitated multicommodity flow network with a single source and multiple sinks, and demands that have known v...
详细信息
ISBN:
(纸本)3540380442
We introduce and study the following model for routing uncertain demands through a network. We are given a capacitated multicommodity flow network with a single source and multiple sinks, and demands that have known values but unknown sizes. We assume that the sizes of demands are governed by independent distributions, and that we know only the means of these distributions and an upper bound on the maximum-possible size. Demands are irrevocably routed one-by-one, and the size of a demand is unveiled only after it is routed. A routing policy is a function that selects an unrouted demand and a path for it, as a function of the residual capacity in the network. Our objective is to maximize the expected value of the demands successfully routed by our routing policy. We distinguish between safe routing policies, which never violate capacity constraints, and unsafe policies, which can attempt to route a demand on any path with strictly positive residual capacity. We design safe routing policies that obtain expected value close to that of an optimal unsafe policy in planar graphs. Unlike most previous work on similar stochastic optimization problems, our routing policies are fundamentally adaptive. Our policies iteratively solve a sequence of linear programs to guide the selection of both demands and routes.
暂无评论