decomposition

Combinatorial Integral Approximation for Mixed-Integer PDE-Constrained Optimization Problems

  • Mirko Hahn
  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , ,

    We apply the basic principles underlying combinatorial integral approximation methods for mixed-integer optimal control with ordinary differential equations in general, and the sum-up rounding algorithm specifically, to optimization problems with partial differential equation (PDE) constraints. By doing so, we identify two possible generalizations that are applicable to problems involving PDE constraints with mesh-dependent integer variables, … Read more

    Stochastic dual dynamic programming with stagewise dependent objective uncertainty

  • Regan Baucke
  • Anthony Downward
  • Oscar Dowson
    • Categories Stochastic Programming Tags , , , ,

    We present a new algorithm for solving linear multistage stochastic programming problems with objective function coefficients modeled as a stochastic process. This algorithm overcomes the difficulties of existing methods which require discretization. Using an argument based on the finiteness of the set of possible cuts, we prove that the algorithm converges almost surely. Finally, we … Read more

    A deterministic algorithm for solving stochastic minimax dynamic programmes

  • Regan Baucke
  • Anthony Downward
  • Golbon Zakeri
    • Categories Dynamic Programming, Robust Optimization, Stochastic Programming Tags , , , , , , , , ,

    In this paper, we present an algorithm for solving stochastic minimax dynamic programmes where state and action sets are convex and compact. A feature of the formulations studied is the simultaneous non-rectangularity of both `min’ and `max’ feasibility sets. We begin by presenting convex programming upper and lower bound representations of saddle functions — extending … Read more

    A deterministic algorithm for solving multistage stochastic programming problems

  • Regan Baucke
  • Anthony Downward
  • Golbon Zakeri
    • Categories Stochastic Programming Tags , , , ,

    Multistage stochastic programming problems are an important class of optimisation problems, especially in energy planning and scheduling. These problems and their solution methods have been of particular interest to researchers in stochastic programming recently. Because of the large scenario trees that these problems induce, current solution methods require random sampling of the tree in order … Read more

    A Decomposition Method for MINLPs with Lipschitz Continuous Nonlinearities

  • Martin Schmidt
  • Mathias Sirvent
  • Winnifried Wollner
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Systems governed by Differential Equations Optimization Tags , , , ,

    Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test … Read more

    Exact penalty decomposition method for zero-norm minimization based on MPEC formulation

  • Xiaolan Liu
  • Shaohua Pan
  • Shujun Shujun
    • Categories Applications - OR and Management Sciences Tags , , ,

    We reformulate the zero-norm minimization problem as an equivalent mathematical program with equilibrium constraints and establish that its penalty problem, induced by adding the complementarity constraint to the objective, is exact. Then, by the special structure of the exact penalty problem, we propose a decomposition method that can seek a global optimal solution of the … Read more

    Combining Penalty-based and Gauss-Seidel Methods for solving Stochastic Mixed-Integer Problems

  • Eberhard Andrew
  • Brian Dandurand
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories Stochastic Programming Tags , , , ,

    In this paper, we propose a novel decomposition approach for mixed-integer stochastic programming (SMIP) problems that is inspired by the combination of penalty-based Lagrangian and block Gauss-Seidel methods (PBGS). In this sense, PBGS is developed such that the inherent decomposable structure that SMIPs present can be exploited in a computationally efficient manner. The performance of … Read more

    Decomposition and Optimization in Constructing Forward Capacity Market Demand Curves

  • Eugene Litvinov
  • Feng Zhao
  • Tongxin Zheng
    • Categories Applications - Science and Engineering, Finance and Economics Tags , , , , , , ,

    This paper presents an economic framework for designing demand curves in Forward Capacity Market (FCM). Capacity demand curves have been recognized as a way to reduce the price volatility inherited from fixed capacity requirements. However, due to the lack of direct demand bidding in FCM, obtaining demand curves that appropriately reflect load’s willingness to pay … Read more

    Decomposition-Based Approximation Algorithms for the One-Warehouse Multi-Retailer Problem with Concave Batch Order Costs

  • Maged M. Dessouky
  • Weihong Hu
  • Alejandro Toriello
  • Zhuoting Yu
    • Categories Approximation Algorithms, Production and Logistics, Supply Chain Management Tags , ,

    We study the one-warehouse multi-retailer (OWMR) problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem … Read more

    Towards Simulation Based Mixed-Integer Optimization with Differential Equations

  • Martin Gugat
  • Günter Leugering
  • Martin Schmidt
  • Mathias Sirvent
  • David Wintergerst
  • Alexander Martin
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Systems governed by Differential Equations Optimization Tags , , , ,

    We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinearity. We prove that … Read more