Month: December 2019

Distributionally Robust Facility Location Problem under Decision-dependent Stochastic Demand

  • Shabbir Ahmed
  • Siqian Shen
  • Beste Basciftci
    • Categories Robust Optimization, Supply Chain Management

    Facility location decisions significantly impact customer behavior and consequently the resulting demand in a wide range of businesses. Furthermore, sequentially realized uncertain demand enforces strategically determining locations under partial information. To address these issues, we study a facility location problem where the distribution of customer demand is dependent on location decisions. We represent moment information … Read more

    Short simplex paths in lattice polytopes

  • Alberto Del Pia
  • Carla Michini
    • Categories Linear Programming, Polyhedra Tags , , ,

    We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The … Read more

    Mathematical Programs with Multiobjective Generalized Nash Equilibrium Problems in the Constraints

  • L Guo
    • Categories Applications - OR and Management Sciences

    This paper considers a class of mathematical programs that include multiobjective generalized Nash equilibrium problems in the constraints. For the lower level, we deal with weakly efficient generalized Nash equilibria. Although this kind of problems has some interesting applications, there is no research focusing on it due to the difficulty resulting from its hierarchical structure … Read more

    Exact and Heuristic Approaches for a New Circular Layout Problem

  • Truden Christian
  • Philipp Hungerländer
  • Kerstin Maier
  • Veronika Pachatz
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Production and Logistics Tags , , , ,

    We discuss a new facility layout problem, the so-called Directed Circular Facility Layout Problem (DCFLP). The DCFLP aims to find an optimal arrangement of machines on a circular material handling system such that the total weighted sum of the center-to-center distances between all pairs of machines measured in clockwise direction is minimized. Several real-world applications, … Read more

    Finite State Approximations for Robust Markov Decision Processes

  • Kerem Ugurlu
    • Categories Applications - OR and Management Sciences

    We give a finite state approximation scheme to countable state controlled robust/risk-averse Markov chains, where there is uncertainty in the transition probability. A convergence theorem along with the corresponding rate for this approximation is established. An approximation to the stationary optimal policy is also given. Our results show a fundamental difference between the finite state … Read more

    Sample Average Approximation for Stochastic Nonconvex Mixed Integer Nonlinear Programming via Outer Approximation

  • David E. Bernal Neira
  • Kevin C Furman
  • Ignacio E. Grossmann
  • Can Li
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , ,

    Stochastic mixed-integer nonlinear programming (MINLP) is a very challenging type of problem. Although there have been recent advances in developing decomposition algorithms to solve stochastic MINLPs, none of the existing algorithms can address stochastic MINLPs with continuous distributions. We propose a sample average approximation-based outer approximation algorithm (SAAOA) that can address nonconvex two-stage stochastic programs … Read more

    Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Clément W. Royer
  • Stephen Wright
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    Worst-case complexity guarantees for nonconvex optimization algorithms have been a topic of growing interest. Multiple frameworks that achieve the best known complexity bounds among a broad class of first- and second-order strategies have been proposed. These methods have often been designed primarily with complexity guarantees in mind and, as a result, represent a departure from … Read more

    Polynomial time guarantees for the Burer-Monteiro method

  • Diego Cifuentes
  • Ankur Moitra
    • Categories Semi-definite Programming Tags , ,

    The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y Y^T$. In this paper, we show that this method can solve SDPs in polynomial … Read more

    Linear Programming using Limited-Precision Oracles

  • Ambros Gleixner
  • Daniel E. Steffy
    • Categories Linear Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations … Read more

    The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment

  • Jonas Egerer
  • Veronika Grimm
  • Thomas Kleinert
  • Martin Schmidt
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

    Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both … Read more