Month: June 2017

Facets for Single Module and Multi-Module Capacitated Lot-Sizing Problems without Backlogging

  • Manish Bansal
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , , , ,

    In this paper, we consider the well-known constant-batch lot-sizing problem, which we refer to as the single module capacitated lot-sizing (SMLS) problem, and multi-module capacitated lot-sizing (MMLS) problem. We provide sufficient conditions under which the (k,l,S,I) inequalities of Pochet and Wolsey (Math of OR 18: 767-785, 1993), the mixed (k,l,S,I) inequalities, derived using mixing procedure … Read more

    Structure and Interpretation of Dual-Feasible Functions

  • Matthias Köppe
  • Jiawei Wang
    • Categories Combinatorial Optimization, Cutting Plane Approaches

    We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory–Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test. Citation 6 pages extended abstract to appear in Proc. LAGOS 2017, with 21 pages of appendix. Article Download View Structure and Interpretation … Read more

    A Robust Optimization Approach for Solving Problems in Conservation Planning

  • Hadi Charkhgard
  • Zulqarnain Haider
  • Changhyun Kwon
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Robust Optimization

    In conservation planning, the data related to size, growth and diffusion of populations is sparse, hard to collect and unreliable at best. If and when the data is readily available, it is not of sufficient quantity to construct a probability distribution. In such a scenario, applying deterministic or stochastic approaches to the problems in conservation … Read more

    A Levenberg-Marquardt method for large nonlinear least-squares problems with dynamic accuracy in functions and gradients

  • Stefania Bellavia
  • Serge Gratton
  • Elisa Riccietti
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags

    In this paper we consider large scale nonlinear least-squares problems for which function and gradient are evaluated with dynamic accuracy and propose a Levenberg-Marquardt method for solving such problems. More precisely, we consider the case in which the exact function to optimize is not available or its evaluation is computationally demanding, but ap- proximations of … Read more

    Revisiting Approximate Linear Programming Using a Saddle Point Approach

  • Qihang Lin
  • Selvaprabu Nadarajah
  • Negar Soheili
    • Categories Dynamic Programming, Semi-infinite Programming, Stochastic Programming Tags , , , , ,

    Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs) arising in applications. VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost, which can be used to assess the suboptimality of heuristic policies. However, … Read more

    Incorporating Black-Litterman Views in Portfolio Construction when Stock Returns are a Mixture of Normals

  • Gérard Cornuéjols
  • Burak Kocuk
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization Tags , , ,

    In this paper, we consider the basic problem of portfolio construction in financial engineering, and analyze how market-based and analytical approaches can be combined to obtain efficient portfolios. As a first step in our analysis, we model the asset returns as a random variable distributed according to a mixture of normal random variables. We then … Read more

    Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization

  • Clément W. Royer
  • Stephen Wright
    • Categories Unconstrained Optimization Tags , , ,

    There has been much recent interest in finding unconstrained local minima of smooth functions, due in part of the prevalence of such problems in machine learning and robust statistics. A particular focus is algorithms with good complexity guarantees. Second-order Newton-type methods that make use of regularization and trust regions have been analyzed from such a … Read more

    Local Convergence of the Heavy-ball Method and iPiano for Non-convex Optimization

  • Peter Ochs
    • Categories Nonsmooth Optimization Tags , , , , , , ,

    A local convergence result for abstract descent methods is proved. The sequence of iterates is attracted by a local (or global) minimum, stays in its neighborhood and converges within this neighborhood. This result allows algorithms to exploit local properties of the objective function. In particular, the abstract theory in this paper applies to the inertial … Read more

    Random projections for linear programming

  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories Linear Programming Tags , ,

    Random projections are random linear maps, sampled from appropriate distributions, that approximately preserve certain geometrical invariants so that the approximation improves as the dimension of the space grows. The well-known Johnson-Lindenstrauss lemma states that there are \LL{random matrices with surprisingly few rows} that approximately preserve pairwise Euclidean distances among a set of points. This is … Read more

    Random projections for trust region subproblems

  • Claudia D'Ambrosio
  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories Linear Programming, Quadratic Programming Tags , ,

    The trust region method is an algorithm traditionally used in the field of derivative free optimization. The method works by iteratively constructing surrogate models (often linear or quadratic functions) to approximate the true objective function inside some neighborhood of a current iterate. The neighborhood is called “trust region” in the sense that the model is … Read more