Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Semi-definite Programming Tags , , , ,

    The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a … Read more

    Efficient Project Scheduling with Autonomous Learning Opportunities

  • Alessandro Hill
  • Thomas Vossen
    • Categories Combinatorial Optimization, Scheduling

    We consider novel project scheduling problems in which the experience gained from completing selected activities can be used to accelerate subsequent activities. Given a set of potential learning opportunities, our model aims to identify the opportunities that result in a maximum reduction of the project makespan when scheduled in sequence. Accounting for the impact of … Read more

    Exploiting cone approximations in an augmented Lagrangian method for conic optimization

  • Mituhiro Fukuda
  • Walter Gómez
  • Gabriel Haeser
  • Leonardo M. Mito
    • Categories Cone Programming, Constrained Nonlinear Optimization Tags , , ,

    We propose an algorithm for general nonlinear conic programming which does not require the knowledge of the full cone, but rather a simpler, more tractable, approximation of it. We prove that the algorithm satisfies a strong global convergence property in the sense that it generates a strong sequential optimality condition. In particular, a KKT point … Read more

    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 study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (BCR) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the BCR formulation on metric instances. A key contribution of our … 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 into … 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

    An algorithmic framework in the criterion space for bi-objective mixed integer linear problems

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

    We propose a flexible and general algorithmic framework for solving 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. Operating in the criterion space, … Read more