A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

  • Jordi Castro
  • Stefano Nasini
  • Francisco Saldanha-da-Gama
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Linear Programming

    We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either … Read more

    Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming

  • Minghui Liu
  • Gabor Pataki
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    We describe simple and exact duals, and certificates of infeasibility and weak infeasibility in conic linear programming which do not rely on any constraint qualification, and retain most of the simplicity of the Lagrange dual. In particular, some of our infeasibility certificates generalize the row echelon form of a linear system of equations, and the … Read more

    Understanding the Convergence of the Alternating Direction Method of Multipliers: Theoretical and Computational Perspectives

  • Jonathan Eckstein
  • Wang Yao
    • Categories Convex Optimization Tags ,

    The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. While it is … Read more

    Generic properties for semialgebraic programs

  • Gue Myung Lee
  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

    In this paper we study genericity for the following parameterized class of nonlinear programs: \begin{eqnarray*} \textrm{minimize } f_u(x) := f(x) – \langle u, x \rangle \quad \textrm{subject to } \quad x \in S, \end{eqnarray*} where $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ is a polynomial function and $S \subset \mathbb{R}^n$ is a closed semialgebraic set, which is … Read more

    Stability and genericity for semi-algebraic compact programs

  • Gue Myung Lee
  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

    In this paper we consider the class of polynomial optimization problems with inequality and equality constraints, in which every problem of the class is obtained by perturbations of the objective function, while the constraint functions are kept fixed. Under certain assumptions, we establish some stability properties (e.g., strong H\”older stability with explicitly determined exponents, semicontinuity, … Read more

    ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex … Read more

    Solving the Probabilistic Traveling Salesman Problem by Linearising a Quadratic Approximation

  • Uwe Clausen
  • J. Fabian Meier
    • Categories Integer Programming, Quadratic Programming, Transportation

    The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The … Read more

    Provably Near-Optimal Approximation Schemes for Implicit Stochastic and for Sample-Based Dynamic Programs

  • Nir Halman
    • Categories Dynamic Programming Tags , , ,

    In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs – the information about the random events is given by value oracles to their CDFs; and sample-based DPs – the information about the random events is deduced via samples. In both models the single period cost functions are … Read more

    A semi-proximal-based strictly contractive Peaceman-Rachford splitting method

  • Yan Gu
  • Deren Han
  • Bo Jiang
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The Peaceman-Rachford splitting method is very efficient for minimizing sum of two functions each depends on its variable, and the constraint is a linear equality. However, its convergence was not guaranteed without extra requirements. Very recently, He et al. (SIAM J. Optim. 24: 1011 – 1040, 2014) proved the convergence of a strictly contractive Peaceman-Rachford … Read more

    Alternating Direction Method of Multipliers for Linear Programming

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Linear Programming Tags , ,

    Recently the alternating direction method of multipliers (ADMM) has been widely used for various applications arising in scientific computing areas. Most of these application models are, or can be easily reformulated as, linearly constrained convex minimization models with separable nonlinear objective functions. In this note we show that ADMM can also be easily used for … Read more