Month: September 2023

A novel Pareto-optimal cut selection strategy for Benders Decomposition

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories (Mixed) Integer Linear Programming Tags ,

    Decomposition methods can be used to create efficient solution algorithms for a wide range of optimization problems. For example, Benders Decomposition can be used to solve scenario-expanded two-stage stochastic optimization problems effectively. Benders Decomposition iteratively generates Benders cuts by solving a simplified version of an optimization problem, the so-called subproblem. The choice of the generated … Read more

    An Integer Programming Approach To Subspace Clustering With Missing Data

  • Akhilesh Soni
  • Jeff Linderoth
  • James R. Luedtke
  • Daniel Pimentel-Alarcon
    • Categories Data Science Algorithms, Integer Programming Tags , ,

    In the Subspace Clustering with Missing Data (SCMD) problem, we are given a collection of n partially observed d-dimensional vectors. The data points are assumed to be concentrated near a union of low-dimensional subspaces. The goal of SCMD is to cluster the vectors according to their subspace membership and recover the underlying basis, which can … Read more

    Resilient Relay Logistics Network Design: A k-Shortest Path Approach

  • Onkar Anand Kulkarni
  • Mathieu Dahan
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , , ,

    Problem definition: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of k-Shortest Path Network Design, which aims to improve a network’s efficiency and resilience through its topological configuration, by locating relay logistics hubs to connect each origin-destination pair with k paths of minimum lengths, weighted by their … Read more

    Error estimate for regularized optimal transport problems via Bregman divergence

  • Keiichi Morikuni
  • Koya Sakakibara
  • AsukaTAKATSU
    • Categories Convex and Nonsmooth Optimization, Linear Programming Tags , , ,

    Regularization by the Shannon entropy enables us to efficiently and approximately solve optimal transport problems on a finite set. This paper is concerned with regularized optimal transport problems via Bregman divergence. We introduce the required properties for Bregman divergences, provide a non-asymptotic error estimate for the regularized problem, and show that the error estimate becomes … Read more

    A Criterion Space Search Feasibility Pump Heuristic for Solving Maximum Multiplicative Programs

  • Ashim Khanal
  • Hadi Charkhgard
    • Categories Game Theory, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    We study a class of nonlinear optimization problems with diverse practical applications, particularly in cooperative game theory. These problems are referred to as Maximum Multiplicative Programs (MMPs), and can be conceived as instances of “Optimization Over the Frontier” in multiobjective optimization. To solve MMPs, we introduce a feasibility pump-based heuristic that is specifically designed to … Read more

    Accelerated Gradient Descent via Long Steps

  • Benjamin Grimmer
  • Kevin Shu
  • Alex L. Wang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Unconstrained Optimization Tags , , , , ,

    Recently Grimmer [1] showed for smooth convex optimization by utilizing longer steps periodically, gradient descent’s state-of-the-art O(1/T) convergence guarantees can be improved by constant factors, conjecturing an accelerated rate strictly faster than O(1/T) could be possible. Here we prove such a big-O gain, establishing gradient descent’s first accelerated convergence rate in this setting. Namely, we … Read more

    Self-concordant Smoothing for Large-Scale Convex Composite Optimization

  • Adeyemi D. Adeoye
  • Alberto Bemporad
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , ,

    We introduce a notion of self-concordant smoothing for minimizing the sum of two convex functions, one of which is smooth and the other may be nonsmooth. The key highlight of our approach is in a natural property of the resulting problem’s structure which provides us with a variable-metric selection method and a step-length selection rule … Read more

    Conjecturing-Based Discovery of Patterns in Data

  • J. Paul Brooks
  • David Edwards
  • C. E. Larson
  • Nico Van Cleemput
    • Categories Applications - OR and Management Sciences, Data Science Algorithms, Optimization in Data Science Tags , , , ,

    We propose the use of a conjecturing machine that suggests feature relationships in the form of bounds involving nonlinear terms for numerical features and boolean expressions for categorical features. The proposed Conjecturing framework recovers known nonlinear and boolean relationships among features from data. In both settings, true underlying relationships are revealed. We then compare the … Read more

    Fast convergence of inertial primal-dual dynamics and algorithms for a bilinearly coupled saddle point problem

  • Phan Vuong
    • Categories Convex Optimization Tags , , , , ,

    This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretization associated with a continuously differentiable bilinearly coupled convex-concave saddle point problem. First, we consider the second-order dynamical system with asymptotically vanishing damping term and show the existence and uniqueness of the trajectories as global twice continuously differentiable … Read more

    DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

  • Yu Yang
    • Categories Branch and Cut Algorithms, Integer Programming, Transportation

    In this paper, we propose an innovative variable fixing strategy called deep Lagrangian underestimate fixing (DeLuxing). It is a highly effective approach for removing unnecessary variables in column-generation (CG)-based exact methods used to solve challenging discrete optimization problems commonly encountered in various industries, including vehicle routing problems (VRPs). DeLuxing employs a novel linear programming (LP) … Read more