More Like this

1. Integrating Machine Learning and Optimization to Boost Decision Making

   Ferdinando, Fioretto (January 2022, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence)

   This paper presents a conceptual review of our recent advancements on the integration of machine learning and optimization. It focuses on describing new hybrid machine learning and optimization methods to predict fast, approximate, solutions to combinatorial problems and to enable structural logical inference. 

   more » « less
2. Entropy-Penalized Semidefinite Programming

   https://doi.org/10.24963/ijcai.2019/157  

   Krechetov, Mikhail; Marecek, Jakub; Maximov, Yury; Takac, Martin (August 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence)

   Low-rank methods for semi-definite programming (SDP) have gained a lot of interest recently, especially in machine learning applications. Their analysis often involves determinant-based or Schatten-norm penalties, which are difficult to implement in practice due to high computational efforts. In this paper, we propose Entropy-Penalized Semi-Definite Programming (EP-SDP), which provides a unified framework for a broad class of penalty functions used in practice to promote a low-rank solution. We show that EP-SDP problems admit an efficient numerical algorithm, having (almost) linear time complexity of the gradient computation; this makes it useful for many machine learning and optimization problems. We illustrate the practical efficiency of our approach on several combinatorial optimization and machine learning problems. 

   more » « less
3. Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities

   Mandi, Jayanta; Kotary, James; Berden, Senne; Mulamba, Maxime; Bucarey, Victor; Guns, Tias; Fioretto, Ferdinando (August 2024, Journal of artificial intelligence research)

   Decision-focused learning (DFL) is an emerging paradigm that integrates machine learning (ML) and constrained optimization to enhance decision quality by training ML models in an end-to-end system. This approach shows significant potential to revolutionize combinatorial decision-making in real-world applications that operate under uncertainty, where estimating unknown parameters within decision models is a major challenge. This paper presents a comprehensive review of DFL, providing an in-depth analysis of both gradient-based and gradient-free techniques used to combine ML and constrained optimization. It evaluates the strengths and limitations of these techniques and includes an extensive empirical evaluation of eleven methods across seven problems. The survey also offers insights into recent advancements and future research directions in DFL. 

   more » « less
4. Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives

   https://doi.org/10.1007/s00453-022-01072-1  

   Asudeh, Abolfazl; Berger-Wolf, Tanya; DasGupta, Bhaskar; Sidiropoulos, Anastasios (December 2022, Algorithmica)

   Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework. 

   more » « less
5. Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems

   B. Wilson, Z. Kudyshev (May 2021, ArXivorg)

   null (Ed.)

   In the recent years, there is a growing interest in using quantum computers for solving combinatorial optimization problems. In this work, we developed a generic, machine learning-based framework for mapping continuous-space inverse design problems into surrogate quadratic unconstrained binary optimization (QUBO) problems by employing a binary variational autoencoder and a factorization machine. The factorization machine is trained as a low-dimensional, binary surrogate model for the continuous design space and sampled using various QUBO samplers. Using the D-Wave Advantage hybrid sampler and simulated annealing, we demonstrate that by repeated resampling and retraining of the factorization machine, our framework finds designs that exhibit figures of merit exceeding those of its training set. We showcase the framework’s performance on two inverse design problems by optimizing (i) thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive meta-gratings for highly efficient beam steering. This technique can be further scaled to leverage future developments in quantum optimization to solve advanced inverse design problems for science and engineering applications. 

   more » « less