Month: May 2019

Indefinite linearized augmented Lagrangian method for convex programming with linear inequality constraints

  • Bingsheng He
  • Shengjie Xu
  • Jing Yuan
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for tackling the convex optimization problem with linear constraints; ALM and its variants for linearly equality-constrained convex minimization models have been well studied in the literatures. However, much less attention has been paid to ALM for efficiently solving the linearly inequality-constrained convex minimization model. In this paper, … Read more

    Projections onto the canonical simplex with additional linear inequalities

  • Lukáš Adam
  • Václav Mácha
    • Categories Quadratic Programming, Robust Optimization

    We consider the distributionally robust optimization and show that computing the distributional worst-case is equivalent to computing the projection onto the canonical simplex with additional linear inequality. We consider several distance functions to measure the distance of distributions. We write the projections as optimization problems and show that they are equivalent to finding a zero … Read more

    Consensus-Based Dantzig-Wolfe Decomposition

  • Shabbir Ahmed
  • Mohamed El Tonbari
    • Categories Linear Programming Tags , ,

    Dantzig-Wolfe decomposition (DWD) is a classical algorithm for solving large-scale linear programs whose constraint matrix involves a set of independent blocks coupled with a set of linking rows. The algorithm decomposes such a model into a master problem and a set of independent subproblems that can be solved in a distributed manner. In a typical … Read more

    A Python package for multi-stage stochastic programming

  • Shabbir Ahmed
  • Lingquan Ding
  • Alexander Shapiro
    • Categories Integer Programming, Optimization Software and Modeling Systems, Stochastic Programming

    This paper presents a Python package to solve multi-stage stochastic linear programs (MSLP) and multi-stage stochastic integer programs (MSIP). Algorithms based on an extensive formulation and Stochastic Dual Dynamic (Integer) Programming (SDDP/SDDiP) method are implemented. The package is synthetically friendly and has a number of features which are not available in the competing software packages. … Read more

    The Nutritious Supply Chain: Optimizing Humanitarian Food Aid

  • Dick den Hertog
  • Ozlem Ergun
  • R Goncalves
  • K Peters
  • H Fleuren
  • M Freeman
  • M Kavelj
  • S Silva
    • Categories Supply Chain Management

    The World Food Programme (WFP) is the largest humanitarian agency fighting hunger worldwide, reaching around 90 million people with food assistance in 80 countries each year. To deal with the operational complexities inherent in its mandate, WFP has been developing tools to assist its decision makers with integrating supply chain decisions across departments and functional … Read more

    A Scenario-Based Approach for the Vehicle Routing Problem with Roaming Delivery Locations under Stochastic Travel Times

  • Joris Kinable
  • Afonso Sampaio
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Meta Heuristics, Stochastic Programming, Transportation Tags , ,

    We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated … Read more

    New characterizations of Hoffman constants for systems of linear constraints

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Polyhedra Tags , ,

    We give a characterization of the Hoffman constant of a system of linear constraints in $\R^n$ relative to a reference polyhedron $R\subseteq\R^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R = \R^n$, we obtain a novel characterization of the classical Hoffman constant. More … Read more

    An Inexact Primal-Dual Smoothing Framework for Large-Scale Non-Bilinear Saddle Point Problems

  • William Haskell
  • Le Thi Khanh Hien
  • Renbo Zhao
    • Categories Convex Optimization Tags , , , ,

    We develop an inexact primal-dual first-order smoothing framework to solve a class of non-bilinear saddle point problems with primal strong convexity. Compared with existing methods, our framework yields a significant improvement over the primal oracle complexity, while it has competitive dual oracle complexity. In addition, we consider the situation where the primal-dual coupling term has … Read more

    Detection and Transformation of Second-Order Cone Programming Problems in a General-Purpose Algebraic Modeling Language

  • Jared Erickson
  • Robert Fourer
    • Categories Modeling Languages and Systems, Second-Order Cone Programming Tags , ,

    Diverse forms of nonlinear optimization problems can be recast to the special form of second-order cone problems (SOCPs), permitting a wider variety of highly effective solvers to be applied. Popular solvers assume, however, that the necessary transformations to required canonical forms have already been identified and carried out. We describe a general approach to the … Read more

    Stochastic Lipschitz Dynamic Programming

  • Shabbir Ahmed
  • Filipe G. Cabral
  • Bernardo Freitas Paulo da Costa
    • Categories Dynamic Programming, Integer Programming, Stochastic Programming Tags , , ,

    We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost to go functions. An example of such a class of cuts are those derived using … Read more