1期

最新文章

• Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs AI翻译
  作者：Gade, Dinakar; Hackebeil, Gabriel; Ryan, Sarah M.; Watson, Jean-Paul; Wets, Roger J. -B.; Woodruff, David L.
  作者单位：United States Department of Energy (DOE); Sandia National Laboratories; Texas A&M University System; Texas A&M University College Station; Iowa State University; University of California System; University of California Davis
  摘要：We present a method for computing lower bounds in the progressive hedging algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using dual prices that are calculated during execution of the standard PHA. We report computational results on stochastic unit commitment and s...
• Total variation bounds on the expectation of periodic functions with applications to recourse approximations AI翻译
  作者：Romeijnders, Ward; van der Vlerk, Maarten H.; Haneveld, Willem K. Klein
  作者单位：University of Groningen
  摘要：We derive a lower and upper bound for the expectation of periodic functions, depending on the total variation of the probability density function of the underlying random variable. Using worst-case analysis we derive tighter bounds for functions that are periodically monotone. These bounds can be used to evaluate the performance of approximations for both continuous and integer recourse models. In this paper, we introduce a new convex approximation for totally unimodular recourse models, and w...
• Single-commodity robust network design with finite and Hose demand sets AI翻译
  作者：Cacchiani, Valentina; Juenger, Michael; Liers, Frauke; Lodi, Andrea; Schmidt, Daniel R.
  作者单位：University of Bologna; University of Cologne; University of Erlangen Nuremberg; Universite de Montreal; Polytechnique Montreal
  摘要：We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming...
• Robust optimization approach for a chance-constrained binary knapsack problem AI翻译
  作者：Han, Jinil; Lee, Kyungsik; Lee, Chungmok; Choi, Ki-Seok; Park, Sungsoo
  作者单位：Universite Catholique Louvain; Korea Advanced Institute of Science & Technology (KAIST); Seoul National University (SNU); Seoul National University (SNU); Hankuk University Foreign Studies
  摘要：We consider a certain class of chance-constrained binary knapsack problem where each item has a normally distributed random weight that is independent of the other items. For this problem we propose an efficient pseudo-polynomial time algorithm based on the robust optimization approach for finding a solution with a theoretical bound on the probability of satisfying the knapsack constraint. Our algorithm is tested on a wide range of random instances, and the results demonstrate that it provides...
• Cutting planes for the multistage stochastic unit commitment problem AI翻译
  作者：Jiang, Ruiwei; Guan, Yongpei; Watson, Jean-Paul
  作者单位：University of Michigan System; University of Michigan; State University System of Florida; University of Florida; United States Department of Energy (DOE); Sandia National Laboratories
  摘要：As renewable energy penetration rates continue to increase in power systems worldwide, new challenges arise for system operators in both regulated and deregulated electricity markets to solve the security-constrained coal-fired unit commitment problem with intermittent generation (due to renewables) and uncertain load, in order to ensure system reliability and maintain cost effectiveness. In this paper, we study a security-constrained coal-fired stochastic unit commitment model, which we use t...
• A cross-decomposition scheme with integrated primal-dual multi-cuts for two-stage stochastic programming investment planning problems AI翻译
  作者：Mitra, Sumit; Garcia-Herreros, Pablo; Grossmann, Ignacio E.
  作者单位：Carnegie Mellon University
  摘要：We describe a cross-decomposition algorithm that combines Benders and scenario-based Lagrangean decomposition for two-stage stochastic programming investment planning problems with complete recourse, where the first-stage variables are mixed-integer and the second-stage variables are continuous. The algorithm is a novel cross-decomposition scheme and fully integrates primal and dual information in terms of primal-dual multi-cuts added to the Benders and the Lagrangean master problems for each ...
• Chance-constrained problems and rare events: an importance sampling approach AI翻译
  作者：Barrera, Javiera; Homem-de-Mello, Tito; Moreno, Eduardo; Pagnoncelli, Bernardo K.; Canessa, Gianpiero
  作者单位：Universidad Adolfo Ibanez; Universidad Adolfo Ibanez; Universidad Adolfo Ibanez
  摘要：We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that varian...
• Minimum cardinality non-anticipativity constraint sets for multistage stochastic programming AI翻译
  作者：Boland, Natashia; Dumitrescu, Irina; Froyland, Gary; Kalinowski, Thomas
  作者单位：University of Newcastle; International Business Machines (IBM); IBM Australia; IBM Research - Australia; University of Melbourne; University of New South Wales Sydney; University of Newcastle; University System of Georgia; Georgia Institute of Technology
  摘要：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 t...
• Decomposition algorithms for two-stage chance-constrained programs AI翻译
  作者：Liu, Xiao; Kucukyavuz, Simge; Luedtke, James
  作者单位：University System of Ohio; Ohio State University; University of Wisconsin System; University of Wisconsin Madison
  摘要：We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where recovery decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve this class of problems. Computational results on a chance-constrained resource planing p...
• Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints AI翻译
  作者：Deng, Yan; Shen, Siqian
  作者单位：University of Michigan System; University of Michigan
  摘要：This paper investigates a problem of scheduling appointments with random service durations on multiple servers with operating time limits. We minimize the cost of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server running overtime. With finite samples of random service time, we consider a mixed-integer linear programming extended formulation and propose a two-stage decomposition framework with cutting planes. The first stage considers a...