Month: September 2022

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more

    Sparse PCA With Multiple Components

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Data Science Theory, Data-Mining, Semi-definite Programming

    Sparse Principal Component Analysis (sPCA) is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner. This involves solving a sparsity and orthogonality-constrained convex maximization problem, which is extremely computationally challenging. Most existing works address sparse PCA via methods—such as iteratively computing … Read more

    Fixed-Point Automatic Differentiation of Forward–Backward Splitting Algorithms for Partly Smooth Functions

  • Sheheryar Mehmood
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    A large class of non-smooth practical optimization problems can be written as minimization of a sum of smooth and partly smooth functions. We consider such structured problems which also depend on a parameter vector and study the problem of differentiating its solution mapping with respect to the parameter which has far reaching applications in sensitivity … Read more

    On the strength of recursive McCormick relaxations for binary polynomial optimization

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any … Read more

    Using Neural Networks to Guide Data-Driven Operational Decisions

  • Ningyuan Chen
  • Saman Lagzi
    • Categories Applications - OR and Management Sciences, Supply Chain Management, Yield Management Tags , , ,

    We propose to use Deep Neural Networks to solve data-driven stochastic optimization problems. Given the historical data of the observed covariate, taken decision, and the realized cost in past periods, we train a neural network to predict the objective value as a function of the decision and the covariate. Once trained, for a given covariate, … Read more

    Shape-Changing Trust-Region Methods Using Multipoint Symmetric Secant Matrices

  • Johannes Brust
  • Jennifer B. Erway
  • Roummel F. Marcia
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this work, we consider methods for large-scale and nonconvex unconstrained optimization. We propose a new trust-region method whose subproblem is defined using a so-called “shape-changing” norm together with densely-initialized multipoint symmetric secant (MSS) matrices to approximate the Hessian. Shape-changing norms and dense initializations have been successfully used in the context of traditional quasi Newton … Read more

    On polynomial time solvability of combinatorial Markov random fields

  • Shaoning Han
  • Andrés Gómez
  • Jong-Shi Pang
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Applications

    The problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled as a mixed-integer program. This motivates us to study a general class of convex submodular optimization problems with indicator variables, which we show to be polynomially solvable in this paper. The key insight is that, possibly after … Read more

    A Machine Learning Approach to Solving Large Bilevel and Stochastic Programs: Application to Cycling Network Design

  • Bo Lin
    • Categories Integer Programming, Stochastic Programming, Transportation Tags , , , ,

    We present a novel machine learning-based approach to solving bilevel programs that involve a large number of independent followers, which as a special case include two-stage stochastic programming. We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. … Read more

    Optimized convergence of stochastic gradient descent by weighted averaging

  • Melinda Hagedorn
  • Florian Jarre
    • Categories Convex Optimization, Data Science Theory, Stochastic Approaches Tags , , , , ,

    Under mild assumptions stochastic gradient methods asymptotically achieve an optimal rate of convergence if the arithmetic mean of all iterates is returned as an approximate optimal solution. However, in the absence of stochastic noise, the arithmetic mean of all iterates converges considerably slower to the optimal solution than the iterates themselves. And also in the … Read more

    A Jacobi-type Newton method for Nash equilibrium problems with descent guarantees

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Oliver Kolossoski
    • Categories Game Theory, Other Topics Tags , , , , ,

    A common strategy for solving an unconstrained two-player Nash equilibrium problem with continuous variables is applying Newton’s method to the system of nonlinear equations obtained by the corresponding first-order necessary optimality conditions. However, when taking into account the game dynamics, it is not clear what is the goal of each player when considering that they … Read more