Month: May 2024

A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set

  • Man-Chung Yue
  • Yves Rychener
  • Daniel Kuhn
  • Viet Anh Nguyen
    • Categories Robust Optimization, Stochastic Programming

    The state-of-the-art methods for estimating high-dimensional covariance matrices all shrink the eigenvalues of the sample covariance matrix towards a data-insensitive shrinkage target. The underlying shrinkage transformation is either chosen heuristically – without compelling theoretical justification – or optimally in view of restrictive distributional assumptions. In this paper, we propose a principled approach to construct covariance … Read more

    On the integrality gap of the Complete Metric Steiner Tree Problem via a novel formulation

  • Ambrogio Maria Bernardelli
  • Eleonora Vercesi
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Luca Maria Gambardella
    • Categories Combinatorial Optimization, Graphs and Matroids, Linear Programming Tags , ,

    In this work, we compute the lower bound of the integrality gap of the Metric Steiner Tree Problem (MSTP) on a graph for some small values of number of nodes and terminals. After debating about some limitations of the most used formulation for the Steiner Tree Problem, namely the Bidirected Cut Formulation, we introduce a … Read more

    On Necessary Optimality Conditions for Sets of Points in Multiobjective Optimization

  • Andrea Cristofari
  • Marianna De Santis
  • Stefano Lucidi
    • Categories Multi-Criteria Optimization Tags , ,

    Taking inspiration from what is commonly done in single-objective optimization, most local algorithms proposed for multiobjective optimization extend the classical iterative scalar methods and produce sequences of points able to converge to single efficient points. Recently, a growing number of local algorithms that build sequences of sets has been devised, following the real nature of … Read more

    Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

  • Jie Wang
    • Categories Optimization in Data Science Tags , ,

    Optimal transport has been very successful for various machine learning tasks; however, it is known to suffer from the curse of dimensionality. Hence, dimensionality reduction is desirable when applied to high-dimensional data with low-dimensional structures. The kernel max-sliced (KMS) Wasserstein distance is developed for this purpose by finding an optimal nonlinear mapping that reduces data … Read more

    Counterfactual Explanations for Linear Optimization

  • Jannis Kurtz
  • Ş. İlker Birbil
  • Dick den Hertog
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , , ,

    The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative. While deriving strong and weak CEs … Read more

    On the accurate detection of the Pareto frontier for bi-objective mixed integer linear problems

  • Lavinia Amorosi
  • Marianna De Santis
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , ,

    We propose a criterion space search algorithm for bi-objective mixed integer linear programming problems. The Pareto frontier of these problems can have a complex structure, as it can include isolated points, open, half-open and closed line segments. Therefore, its exact detection is an achievable though hard computational task. Our algorithm works by alternating the resolution … Read more

    Scheduling Bodyguards

  • Loe Schlicher
    • Categories Game Theory Tags , ,

    Security agencies throughout the world use bodyguards to protect government officials and public figures. In this paper, we consider a two-person zero-sum game between a defender who allocates such bodyguards to protect several targets and an attacker who chooses one target to attack. Because the number of feasible bodyguard allocations grows quickly as either the … Read more

    Relay-Hub Network Design for Consolidation Planning Under Demand Variability

  • Onkar Anand Kulkarni
  • Mathieu Dahan
    • Categories Branch and Cut Algorithms, Supply Chain Management, Transportation Tags , , , , , ,

    Problem description: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of Capacitated Relay Network Design under Stochastic Demand and Consolidation-Based Routing (CRND-SDCR), which aims to improve a network’s efficiency and resilience against commodity demand variability through integrating tactical decisions. Methodology: We formulate CRND-SDCR as a two-stage stochastic … Read more

    Sensitivity Analysis in Dantzig-Wolfe Decomposition

  • Kouhei Harada
    • Categories Linear Programming Tags , , ,

    Dantzig-Wolfe decomposition is a well-known classical method for solving huge linear optimization problems with a block-angular structure. The most computationally expensive process in the method is pricing: solving block subproblems for a dual variable to produce new columns. Therefore, when we want to solve a slightly perturbated problem in which the block-angular structure is preserved … Read more