Month: February 2014

Applying oracles of on-demand accuracy in two-stage stochastic programming – a computational study

  • Csaba I. Fábián
  • Achim Koberstein
  • Leena Suhl
  • Christian Wolf
    • Categories Optimization Software Benchmark, Stochastic Programming Tags , , ,

    Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the single-cut and the multi-cut version. The concept of an oracle with on-demand accuracy was originally proposed in the context of bundle methods for unconstrained convex optimzation to provide approximate function data and subgradients. In … Read more

    Decomposition Algorithm for Optimizing Multi-server Appointment Scheduling with Chance Constraints

  • Yan Deng
  • Siqian Shen
    • Categories Cutting Plane Approaches, Stochastic Programming

    We schedule appointments with random service durations on multiple servers with operating time limits. We minimize the costs of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server overtime. Using finite samples of the uncertainty, we formulate the problem as a mixed-integer linear program, and propose a two-stage … Read more

    Joint Variable Selection for Data Envelopment Analysis via Group Sparsity

  • Zhiwei (Tony) Qin
  • Irene Song
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , ,

    This study develops a data-driven group variable selection method for data envelopment analysis (DEA), a non-parametric linear programming approach to the estimation of production frontiers. The proposed method extends the group Lasso (least absolute shrinkage and selection operator) designed for variable selection on (often predefined) groups of variables in linear regression models to DEA models. … Read more

    An improved Kalai-Kleitman bound for the diameter of a polyhedron

  • Michael J. Todd
    • Categories Linear Programming Tags ,

    Kalai and Kleitman established the bound $n^{\log(d) + 2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d)^{\log(d)}$. Citation School of Operations Research and Information Engineering, Cornell University, Ithaca NY, USA, February 2014 Article Download View An improved Kalai-Kleitman bound for the diameter of a polyhedron

    Bound Improvement for LNG Inventory Routing

  • Kevin C Furman
  • Vikas Goel
  • Samid Hoda
  • Yufen Shao
    • Categories Applications - OR and Management Sciences, Supply Chain Management, Transportation

    Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. In this paper, we develop methods for improving both lower and upper bounds for a previously stated form of an LNG inventory routing problem. A Dantzig-Wolfe-based decomposition approach is developed for LNG inventory routing problem (LNG-IRP) attempting to overcome poor lower … Read more

    An Accelerated Linearized Alternating Direction Method of Multipliers

  • Yunmei Chen
  • Guanghui Lan
  • Yuyuan Ouyang
  • Eduardo Pasiliao Jr.
    • Categories Convex Optimization Tags , , , ,

    We present a novel framework, namely AADMM, for acceleration of linearized alternating direction method of multipliers (ADMM). The basic idea of AADMM is to incorporate a multi-step acceleration scheme into linearized ADMM. We demonstrate that for solving a class of convex composite optimization with linear constraints, the rate of convergence of AADMM is better than … Read more

    Optimal subgradient algorithms with application to large-scale linear inverse problems

  • Masoud Ahookhosh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , , , , ,

    This study addresses some algorithms for solving structured unconstrained convex optimization problems using first-order information where the underlying function includes high-dimensional data. The primary aim is to develop an implementable algorithmic framework for solving problems with multi-term composite objective functions involving linear mappings using the optimal subgradient algorithm, OSGA, proposed by {\sc Neumaier} in \cite{NeuO}. … Read more

    OSGA: A fast subgradient algorithm with optimal complexity

  • Arnold Neumaier
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst … Read more

    String-Averaging Expectation-Maximization for Maximum Likelihood Estimation in Emission Tomography

  • Yair Censor
  • Álvaro Rodolfo De Pierro
  • Elias Salomão Helou
  • Tai-Been Chen
  • I-Liang Chern
  • Ming Jiang
  • Henry Horng-Shing Lu
    • Categories Biomedical Applications, Convex Optimization Tags , , , , , ,

    We study the maximum likelihood model in emission tomography and propose a new family of algorithms for its solution, called String-Averaging Expectation-Maximization (SAEM). In the String-Averaging algorithmic regime, the index set of all underlying equations is split into subsets, called “strings,” and the algorithm separately proceeds along each string, possibly in parallel. Then, the end-points … Read more

    Planning for Mining Operations with Time and Resource Constraints

  • Christina Burt
  • Peter J. Stuckey
  • Nir Lipovetzky
  • Adrian R. Pearce
    • Categories Production and Logistics, Scheduling, Transportation Tags , , ,

    We study a daily mine planning problem where, given a set of blocks we wish to mine, our task is to generate a mining sequence for the excavators such that blending resource constraints are met at various stages of the sequence. Such time-oriented resource constraints are not traditionally handled well by automated planners. On the … Read more