检索结果-内蒙古大学图书馆

two-stage stochastic minimum s - t cut problems: Formulations, complexity and decomposition algorithms

NEtwoRKS 2020年第3期75卷 235-258页

作者： Steffen, Rebennack Prokopyev, Oleg A. Singh, Bismark Karlsruhe Inst Technol Inst Operat Res Dept Stochast Optimizat Karlsruhe Germany Univ Pittsburgh Dept Ind Engn Pittsburgh PA USA Friedrich Alexander Univ Erlangen Nurnberg Discrete Math Erlangen Germany

We introduce the two-stage stochastic minimum s - t cut problem. Based on a classical linear 0-1 programming model for the deterministic minimum s - t cut problem, we provide a mathematical programming formulation for the proposed stochastic extension. We show that its constraint matrix loses the total unimodularity property, however, preserves it if the considered graph is a tree. This fact turns out to be not surprising as we prove that the considered problem is NP-hard in general, but admits a linear time solution algorithm when the graph is a tree. We exploit the special structure of the problem and propose a tailored Benders decomposition algorithm. We evaluate the computational efficiency of this algorithm by solving the Benders dual subproblems as max-flow problems. For many tested instances, we outperform a standard Benders decomposition by two orders of magnitude with the Benders decomposition exploiting the max-flow structure of the subproblems.

关键词： Benders decomposition combinatorial optimization complexity minimum s - t cut problem total unimodularity two-stage stochastic programming

来源：评论

学校读者我要写书评

暂无评论

A shortage risk mitigation model for multi-agency coordination in logistics planning

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 148卷 106676-106676页

作者： Rodriguez-Espindola, Oscar Alem, Douglas Da Silva, Lucas Pelegrin Aston Business Sch OIM Grp Birmingham B4 7ET W Midlands England Univ Edinburgh Business Sch 29 Buccleuch Pl Edinburgh EH8 9JS Midlothian Scotland Univ Fed Sao Carlos Prod Engn Dept Sorocaba Brazil

We introduce a two-stage stochastic program to handle typical disaster preparedness activities under uncertainty from a multi-agency perspective. The model explicitly takes into account the number of people without healthcare attention, relief aid, and shelter support. We build a function that represents the total number of people at risk of not receiving proper humanitarian assistance using a bi-objective approach in which expected logistics costs are also minimized. The benefit of our approach is assessed through real flood cases in Mexico in which GIS analysis was used to enhance data gathering and to provide risk maps that could be potentially used by policy-makers in practical settings. The overall results suggest that sheltering decisions have to be closely coordinated with the management of material and human resources to avoid an increased number of people deprived of attention and relief aid. The Pareto Frontier also reveals that some solutions exhibit a quite interesting trade-off, e.g., it is possible to improve the overall relief assistance by almost 17% at the expense of less than 14% in the logistics costs.

关键词： Disaster relief Humanitarian logistics Preparedness management Multi-agency coordination two-stage stochastic programming

来源：评论

学校读者我要写书评

暂无评论

A participatory approach based on stochastic optimization for the spatial allocation of Sustainable Urban Drainage Systems for rainwater harvesting

引用

ENVIRONMENTAL MODELLING & SOFTWARE 2020年 123卷 104532-000页

作者： Narine Torres, Maria Fontecha, John E. Zhu, Zhenduo Walteros, Jose L. Pablo Rodriguez, Juan Univ Los Andes CIIA Bogota Colombia SUNY Buffalo Dept Civil Struct & Environm Engn Buffalo NY USA SUNY Buffalo Ind Engn Dept GAMMA Buffalo NY USA

Rainwater Harvesting (RWH) is the practice of capturing and storing stormwater for later use. In addition to being an alternative source of water for non-potable applications, RWH is also used to effectively reduce stormwater runoff volumes and pollutant loads dropped into sewage systems. RWH is typically carried out by placing a variety of Sustainable Urban Drainage Systems (SUDS) in different locations of the urban landscape. However, because of the staggering number of potential combinations of SUDS typologies and spatial configurations that can be used, identifying a strategy that optimally selects and allocates SUDS to maximize the benefits of RWH is a complex endeavor. One of the challenges that emerges during the optimal design and location of these systems is incorporating the inherent uncertainty of the rainfall. In this paper, we develop a flexible computational framework that couples a Geographic Information System (GIS) with a two-stage stochastic mixed integer linear program (TS-MILP) to select and locate SUDS in order to minimize the use of potable water for irrigation and reduce the water runoff at a minimum cost. This framework incorporates an iterative participatory approach to engage stakeholders in the decision-making process. We tested the proposed methodology on a case study for the central campus at Universidad de Los Andes (Bogota, Colombia). Our results showed that the expected value of the total runoff volume and the consumption of potable water can be reduced up to 67% and 50%, respectively.

关键词： Mixed integer program Participatory approach Rainwater harvesting Stormwater recycling Sustainable urban drainage systems two-stage stochastic programming

来源：评论

学校读者我要写书评

暂无评论

An accelerated L-shaped method for solving two-stage stochastic programs in disaster management

引用

ANNALS OF OPERATIONS RESEARCH 2020年第2期284卷 557-582页

作者： Grass, Emilia Fischer, Kathrin Rams, Antonia Hamburg Univ Technol Inst Operat Res & Informat Syst Schwarzenberg Campus 4 D-21073 Hamburg Germany

Mitigating the disastrous effects of natural disasters by performing preparation activities is one of the main purposes of relief organizations. However, the high degree of uncertainty associated with disasters impedes the work of aid agencies considerably. In this regard, two-stage stochastic programs are often used in the relevant literature to support decision making in these situations. An accelerated L-shaped method is proposed in this work, which solves realistic large-scale two-stage stochastic problems within a reasonable time-frame, allowing relief organizations to react to short-term forecasts, as e.g. available in case of hurricanes or floods. In particular, computation times needed for solving the resulting sub-problems via a specialized interior-point method are significantly reduced by exploiting the specific structure of second-stage constraints. To show the superiority of this approach with respect to solution times, a realistic large-scale case study is developed for America's hurricane-prone south-east coast. The accelerated L-shaped method outperforms the standard L-shaped method significantly whereas a commercial solver failed to solve the case study within an acceptable time-frame.

关键词： L-shaped method stochastic Benders decomposition Interior-point methods two-stage stochastic programming Disaster management

来源：评论

学校读者我要写书评

暂无评论

A stochastic two-stage Model for the Integrated Scheduling of the Electric and Natural Gas Systems

IEEE OPEN ACCESS JOURNAL OF POWER AND ENERGY

引用

IEEE OPEN ACCESS JOURNAL OF POWER AND ENERGY 2020年 7卷 453-466页

作者： Kanelakis, Nikolaos G. Biskas, Pandelis N. Chatzigiannis, Dimitris, I Bakirtzis, Anastasios G. Aristotle Univ Thessaloniki Dept Elect & Comp Engn Thessaloniki 54124 Greece Heron II Viotias SA Athens 11526 Greece

The inherent coupling of the electric and natural gas systems due to the operation of gas generating units and power-to-gas facilities, along with the uncertainties faced in both systems due to the variability in electricity and gas demand and the vastly increasing volatile renewable injections, create an imperative need to schedule and operate the two systems in a coordinated manner. In this paper a new model for the fully integrated stochastic day-ahead scheduling of electric and gas systems is presented, coping with the uncertainties of both systems. The stochastic parameters comprise the electricity demand and the renewable injections, which collectively create several net electricity load scenarios, and the gas residential/industrial demand. The integrated scheduling problem concerns a unit commitment for the electricity problem, amended with additional constraints imposed by the underlying natural gas transmission system considering steady-state flow. A two-stage stochastic programming model is devised, having as second stage the possible realizations of net electricity load and gas demand in real-time. The model is tested in medium-size real-world test systems - the Greek electricity and gas systems - deriving useful insights on the advantages of the integrated stochastic scheduling versus the deterministic scheduling of the electricity and gas systems.

关键词： Electricity system natural gas system integrated scheduling mixed integer linear programming two-stage stochastic programming

来源：评论

学校读者我要写书评

暂无评论

A data-driven approach for supply chain network design under uncertainty with consideration of social concerns

引用

ANNALS OF OPERATIONS RESEARCH 2020年第1期288卷 265-284页

作者： Fattahi, Mohammad Shahrood Univ Technol Dept Ind Engn & Management Shahrood Iran

Although supply chain network design under uncertainty has been studied by many researchers, most stochastic programming approaches in this area assume uncertain parameters follow certain distribution functions. However, in practice, the true distributions may be ambiguous and some historical data are available. This study proposes a data-driven two-stage stochastic programming model to obtain robust decisions among all possible distributions in a defined ambiguity set based on the moments of available data. In accordance with the proposed stochastic program, a solution algorithm based on Benders' decomposition is developed. Further, the social concerns corresponding to the supply chain network are derived and quantified by the social life cycle assessment methodology. The proposed model is applied for designing a recovery network in which various technologies use generated municipal solid wastes for the power generation. Computational results on a real-life case study demonstrate the applicability of the proposed data-driven two-stage stochastic model as well as the impact of considering social concerns on the design decisions.

关键词： Supply chain network design Data driven two-stage stochastic programming Social-life cycle assessment Social concerns

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Envelope Constrained Multiperiod stochastic Emergency Medical Services Location Model and Decomposition Scheme

引用

TRANSPORTATION SCIENCE 2020年第6期54卷 1471-1494页

作者： Peng, Chun Delage, Erick Li, Jinlin HEC Montreal Montreal PQ H3T 2A7 Canada GERAD Montreal PQ H3T 2A7 Canada Beijing Inst Technol Beijing 100081 Peoples R China

This paper considers a multiperiod emergency medical services (EMS) location problem and introduces two two-stage stochastic programming formulations that account for uncertainty about emergency demand. Whereas the first model considers both a constraint on the probability of covering the realized emergency demand and minimizing the expected cost of doing so, the second one employs probabilistic envelope constraints that allow us to control the degradation of coverage under the more severe scenarios. These models give rise to large mixed-integer programs, which can be tackled directly or by using a conservative approximation scheme. For the former, we implement the branch-and-Benders-cut method, which improves significantly the solution time when compared with using both a recently proposed state-of-the art branch-and-bound algorithm and the CPLEX solver. Finally, a practical study is conducted using historical data from the Northern Ireland Ambulance Service and sheds some light on optimal EMS location configuration for this region and on necessary trade-offs that must be made between emergency demand coverage and expected cost. These insights are confirmed through an out-of-sample performance analysis.

关键词： facility location two-stage stochastic programming chance-constrained programming probabilistic envelope constraint emergency medical services location branch-and-benders-cut

来源：评论

学校读者我要写书评

暂无评论

A two-step stochastic approach for operating rooms scheduling in multi-resource environment

引用

ANNALS OF OPERATIONS RESEARCH 2020年第1期292卷 191-214页

作者： Atighehchian, Arezoo Sepehri, Mohammad Mehdi Shadpour, Pejman Kianfar, Kamran Univ Isfahan Fac Adm Sci & Econ Dept Management Esfahan *** Iran Tarbiat Modares Univ Dept Ind Engn Tehran *** Iran Iran Univ Med Sci Hosp Management Res Ctr Hasheminejad Kidney Ctr Tehran Iran Univ Isfahan Fac Engn Esfahan *** Iran

Planning and scheduling of operating rooms (ORs) is important for hospitals to improve efficiency and achieve high quality of service. Due to significant uncertainty in surgery durations, scheduling of ORs can be very challenging. In this paper, surgical case scheduling problem with uncertain duration of surgeries in multi resource environment is investigated. We present a two-stage stochastic mixed-integer programming model, named SOS, with the objective of total ORs idle time and overtime. Also, in this paper a two-step approach is proposed for solving the model based on the L-shaped algorithm. Proposing the model in a multi resources environment with considering real-life limitations in academic hospitals and developing an approach for solving this stochastic model efficiently form the main contributions of this paper. The model is evaluated through several numerical experiments based on real data from Hasheminejad Kidney Center (HKC) in Iran. The solutions of SOS are compared with the deterministic solutions in several real instances. Numerical results show that SOS enjoys a better performance in 97% of the cases. Furthermore, the results of comparing with actual schedules applied in HKC reveal a notable reduction of OR idle time and over time which illustrate the efficiency of the proposed model in practice.

关键词： Operating room Scheduling two-stage stochastic programming L-shaped algorithm

来源：评论

学校读者我要写书评

暂无评论

Quantifying resilience in energy systems with out-of-sample testing

引用

APPLIED ENERGY 2021年 285卷 116465-116465页

作者： Pickering, Bryn Choudhary, Ruchi Univ Cambridge Dept Engn Cambridge England Swiss Fed Inst Technol Climate Policy Grp Zurich Switzerland Alan Turing Inst Data Centr Engn London England

The need to design resilient energy systems becomes ever more apparent as we face the challenge of decarbonising through reliance on non-dispatchable technologies and sectoral integration. Increasingly, modelling efforts focus on improving system resilience, but fail to quantify the improvements. In this paper, we propose a novel workflow that allows increases in resilience to be measured quantitatively. It incorporates out-of-sample testing following optimisation, and compares the impacts of demand and power interruption uncertainty on both risk-unaware and risk-aware district energy system models. To ensure we encompass the full range of impacts caused by uncertainty, we consider nine distinct objectives encompassing differences in: investment and operation costs, CO2 emissions, and aversion to risk. We apply the workflow in a case study in Bangalore, India, and demonstrate that scenario optimisation improves system resilience by one to two orders of magnitude. However, systems designed for resilience to demand uncertainty are not able to gracefully extend to managing risk from extreme shocks to the system, such as power interruptions. We show that shock-induced instability can be addressed by specific measures to reduce grid dependence. Finally, by studying out-of-sample test results, we identify an objective which balances cost, CO2 emissions, and system resilience;this balance is achieved by novel application of the Conditional Value at Risk measure. These results expose the need for out-of-sample testing whenever uncertainty is considered in energy system modelling, and we provide the framework with which it can be undertaken.

关键词： District energy systems Mixed integer linear optimisation Out-of-sample testing Resilient systems Scenario optimisation two-stage stochastic programming

来源：评论

学校读者我要写书评

暂无评论

Designing a municipal solid waste management system under disruptions using an enhanced L-shaped method

引用

JOURNAL OF CLEANER PRODUCTION 2021年 299卷 126672-126672页

作者： Zarrinpoor, Naeme Pishvaee, Mir Saman Shiraz Univ Technol Dept Ind Engn POB 71555-313Modarres Blvd Shiraz Iran Iran Univ Sci & Technol Sch Ind Engn Tehran Iran

This study addresses a novel two-stage possibilistic-stochastic programming model for designing a reliable municipal solid waste management system (MSWMS) in the presence of random disruptions arising from unexpected natural and man-made hazards and imprecision arising from the lack of knowledge about some input parameters. To design a profit-maximizing and environment-friendly MSWMS, an integrated system is worked out to provide revenues through producing renewable energy, fertilizers, and recycled products from processing municipal solid wastes. To solve the proposed model in large-scale instances, an L-shaped method is designed in which several enhancement strategies such as valid inequalities, local branching, and primal heuristics are developed to expedite the convergence rate. The proposed model is validated through a real case study of the MSWMS in the city of Shiraz, Iran. Compared with traditional models with the consideration of only normal disruption-free conditions, the expected profit of the proposed model drops down slightly but the system will hedge against the risk of different disruptions. The optimal network configuration is strongly affected by disruptive conditions such that the number of constructed facilities is increased and they are moved to more reliable locations. Moreover, when designing reliable MSWMSs from economic, environmental, and risk perspectives is approached, the system will incur more costs. The proposed solution procedure also proves to be effective in finding good quality solutions within a short running time for large-scale instances that are far beyond the reach of CPLEX. ? 2021 Elsevier Ltd. All rights reserved.

关键词： Municipal solid waste management Disruption two-stage stochastic programming L-shaped method Enhancement strategies

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：