Strong Duality and Dual Pricing Properties in Semi-infinite Linear Programming–A Non-Fourier-Motzkin Elimination Approach

  • Qinghong Zhang
    • Categories Semi-infinite Programming

    The Fourier-Motzkin elimination method has been recently extended to linear inequality systems that have infinitely many inequalities. It has been used in the study of linear semi-infinite programming by Basu, Martin, and Ryan. Following the idea of the conjecture for semi-infinite programming in a paper by Kortanek and Zhang recently published in Optimization, which states … Read more

    An O(nm) time algorithm for finding the min length directed cycle in a graph

  • James B. Orlin
  • Antonio Sedeño-Noda
    • Categories Graphs and Matroids, Network Optimization, Optimization Software and Modeling Systems Tags , ,

    In this paper, we introduce an $O(nm)$ time algorithm to determine the minimum length directed cycle in a directed network with $n$ nodes and $m$ arcs and with no negative length directed cycles. This result improves upon the previous best time bound of $O(nm + n^2 \log\log n)$. Our algorithm first determines the cycle with … Read more

    An empirical analysis of scenario generation methods for stochastic optimization

  • Nils Löhndorf
    • Categories Stochastic Programming Tags , , , , , , ,

    This work presents an empirical analysis of popular scenario generation methods for stochastic optimization, including quasi-Monte Carlo, moment matching, and methods based on probability metrics, as well as a new method referred to as Voronoi cell sampling. Solution quality is assessed by measuring the error that arises from using scenarios to solve a multi-dimensional newsvendor … Read more

    A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization

  • Hübner Jens
  • Martin Schmidt
  • Marc C. Steinbach
    • Categories Finance and Economics, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate … Read more

    Gap functions for quasi-equilibria

  • Giancarlo Bigi
  • Mauro Passacantando
    • Categories Complementarity and Variational Inequalities, Game Theory, Nonsmooth Optimization Tags , , , ,

    An approach for solving quasi-equilibrium problems (QEPs) is proposed relying on gap functions, which allow reformulating QEPs as global optimization problems. The (generalized) smoothness properties of a gap function are analysed and an upper estimates of its Clarke directional derivative is given. Monotonicity assumptions on both the equilibrium and constraining bifunctions are a key tool … Read more

    City Logistics: Challenges and Opportunities

  • Martin Savelsbergh
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Production and Logistics, Transportation Tags , , , , , ,

    Today, around 54% of the world’s population lives in urban areas. By 2050, this share is expected to go up significantly. As a result, city logistics, which focuses on the efficient and effective transportation of goods in urban areas while taking into account the negative effects on congestion, safety, and environment, is critical to ensuring … Read more

    Exploiting Optimization for Local Graph Clustering

  • Roosta-Khorasani Farbod
  • Kimon Fountoulakis
  • Shun Julian
  • Mahoney Michael
  • Cheng Xiang
    • Categories Approximation Algorithms, Convex and Nonsmooth Optimization, Graphs and Matroids

    Local graph clustering methods aim to identify well-connected clusters around a given “seed set” of reference nodes. The main focus of prior theoretical work has been on worst-case running time properties or on implicit statistical regularization; and the focus of prior empirical work has been to identify structure in large social and information networks. Here, … Read more

    Min-max-min Robust Combinatorial Optimization Subject to Discrete Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories 0-1 Programming, Combinatorial Optimization, Robust Optimization Tags , ,

    We consider combinatorial optimization problems with uncertain objective functions. In the min-max-min robust optimization approach, a fixed number k of feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate a set of candidate solutions in a potentially expensive preprocessing and then select … Read more

    Solving rank-constrained semidefinite programs in exact arithmetic

  • Simone Naldi
    • Categories Semi-definite Programming Tags , , , , , , , ,

    We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in … Read more

    An Algorithmic Framework of Generalized Primal-Dual Hybrid Gradient Methods for Saddle Point Problems

  • Bingsheng He
  • Feng Ma
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    The primal-dual hybrid gradient method (PDHG) originates from the Arrow-Hurwicz method, and it has been widely used to solve saddle point problems, particularly in image processing areas. With the introduction of a combination parameter, Chambolle and Pock proposed a generalized PDHG scheme with both theoretical and numerical advantages. It has been analyzed that except for … Read more