Month: July 2017

Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools

  • Joey Huchette
  • Juan Pablo Vielma
    • Categories Integer Programming Tags ,

    We present novel mixed-integer programming (MIP) formulations for (nonconvex) piecewise linear functions. Leveraging recent advances in the systematic construction of MIP formulations for disjunctive sets, we derive new formulations for univariate functions using a geometric approach, and for bivariate functions using a combinatorial approach. All formulations derived are small (logarithmic in the number of piecewise … Read more

    Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method)

  • Pavel Dvurechensky
  • Alexander Gasnikov
  • Alexander Tiurin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , ,

    In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. … Read more

    Benders decomposition of the resource constrained project scheduling problem

  • Se Terblanche
  • JH van Vuuren
    • Categories Branch and Cut Algorithms, Scheduling

    Problem instances found in the literature that are used in computational studies of the resource constrained project scheduling problem, typically include only a few resources. In some practical applications, however, the number of resources may be significantly higher. In this paper, problem instances with a large number of resources are considered and a Benders decomposition … Read more

    Convergence of first-order methods via the convex conjugate

  • Javier F. Peña
    • Categories Convex Optimization Tags ,

    This paper gives a unified and succinct approach to the $O(1/\sqrt{k}), O(1/k),$ and $O(1/k^2)$ convergence rates of the subgradient, gradient, and accelerated gradient methods for unconstrained convex minimization. In the three cases the proof of convergence follows from a generic bound defined by the convex conjugate of the objective function. Citation Working Paper, Carnegie Mellon … Read more

    Substation Location and Transmission Network Expansion Problem in Power System

  • Bahar Y. Kara
  • Ayse Selin Kocaman
  • Meltem Peker
    • Categories Network Optimization Tags , , ,

    In this paper, we propose a model for the generation and transmission network expansion planning problem that includes decisions related to substations’ locations and sizes. In power system expansion planning problems, locations of generation units and/or transmission lines are determined. However, substation location decisions are not explicitly studied. Nevertheless, including the decisions of substations’ locations … Read more

    A Robust Multi-Batch L-BFGS Method for Machine Learning

  • Albert S. Berahas
  • Martin Takac
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper describes an implementation of the L-BFGS method designed to deal with two adversarial situations. The first occurs in distributed computing environments where some of the computational nodes devoted to the evaluation of the function and gradient are unable to return results on time. A similar challenge occurs in a multi-batch approach in which … Read more

    Crowdshipping and Same-day Delivery: Employing In-store Customers to Deliver Online Orders

  • Iman Dayarian
  • Martin Savelsbergh
    • Categories Applications - OR and Management Sciences, Transportation Tags , , , ,

    Same-day delivery of online orders is becoming an indispensable service for large retailers. We explore an environment in which in-store customers supplement company drivers and can take on the task of delivering online orders on their way home. Because online orders as well as in-store customers willing to make deliveries arrive throughout the day, it … Read more

    Mathematical models for Multi Container Loading Problems with practical constraints

  • M.T Alonso
  • Ramon Alvarez-Valdes
  • Manuel Iori
  • F. Parreño
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , ,

    We address the multi container loading problem of a company that has to serve its customers by first putting the products on pallets and then loading the pallets into trucks. We approach the problem by developing and solving integer linear models. To be useful in practice, our models consider three types of constraints: geometric constraints, … Read more

    On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods

  • Gabriel Haeser
  • Yinyu Ye
  • Oliver Hinder
    • Categories Nonlinear Optimization Tags , , , ,

    This paper analyzes sequences generated by infeasible interior point methods. In convex and non-convex settings, we prove that moving the primal feasibility at the same rate as complementarity will ensure that the Lagrange multiplier sequence will remain bounded, provided the limit point of the primal sequence has a Lagrange multiplier, without constraint qualification assumptions. We … Read more

    A deterministic algorithm for solving multistage stochastic programming problems

  • Regan Baucke
  • Anthony Downward
  • Golbon Zakeri
    • Categories Stochastic Programming Tags , , , ,

    Multistage stochastic programming problems are an important class of optimisation problems, especially in energy planning and scheduling. These problems and their solution methods have been of particular interest to researchers in stochastic programming recently. Because of the large scenario trees that these problems induce, current solution methods require random sampling of the tree in order … Read more