Solving Recurrent MIPs with Semi-supervised Graph Neural Networks

• URL: http://arxiv.org/abs/2302.11992v1
• Date: Mon, 20 Feb 2023 15:57:56 GMT
• Title: Solving Recurrent MIPs with Semi-supervised Graph Neural Networks
• Authors: Konstantinos Benidis, Ugo Rosolia, Syama Rangapuram, George Iosifidis, Georgios Paschos
• Abstract summary: We propose an ML-based model that automates and expedites the solution of MIPs by predicting the values of variables. Our approach is motivated by the observation that many problem instances share salient features and solution structures. Examples include transportation and routing problems where decisions need to be re-optimized whenever commodity volumes or link costs change.
• Score: 15.54959083707859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an ML-based model that automates and expedites the solution of MIPs by predicting the values of variables. Our approach is motivated by the observation that many problem instances share salient features and solution structures since they differ only in few (time-varying) parameters. Examples include transportation and routing problems where decisions need to be re-optimized whenever commodity volumes or link costs change. Our method is the first to exploit the sequential nature of the instances being solved periodically, and can be trained with ``unlabeled'' instances, when exact solutions are unavailable, in a semi-supervised setting. Also, we provide a principled way of transforming the probabilistic predictions into integral solutions. Using a battery of experiments with representative binary MIPs, we show the gains of our model over other ML-based optimization approaches.

Related papers

• Dynamical Measure Transport and Neural PDE Solvers for Sampling [77.38204731939273]
  We tackle the task of sampling from a probability density as transporting a tractable density function to the target. We employ physics-informed neural networks (PINNs) to approximate the respective partial differential equations (PDEs) solutions. PINNs allow for simulation- and discretization-free optimization and can be trained very efficiently.
  arXiv  Detail & Related papers  (2024-07-10T17:39:50Z)
• Regression-aware Inference with LLMs [52.764328080398805]
  We show that an inference strategy can be sub-optimal for common regression and scoring evaluation metrics. We propose alternate inference strategies that estimate the Bayes-optimal solution for regression and scoring metrics in closed-form from sampled responses.
  arXiv  Detail & Related papers  (2024-03-07T03:24:34Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  We present an integrated prediction-optimization (PredOpt) framework to efficiently solve sequential decision-making problems. We address the key issues of sequential dependence, infeasibility, and generalization in machine learning (ML) to make predictions for optimal solutions to instances problems.
  arXiv  Detail & Related papers  (2023-11-12T21:54:53Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  We study the problem of single-channel source separation (SCSS) We focus on cyclostationary signals, which are particularly suitable in a variety of application domains. We propose a deep learning approach using a U-Net architecture, which is competitive with the minimum MSE estimator.
  arXiv  Detail & Related papers  (2022-08-22T14:04:56Z)
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
  Mixed-integer programming (MIP) technology offers a generic way of formulating and solving optimization problems. MIP-GNN is a general framework for enhancing such solvers with data-driven insights. We integrate MIP-GNN into a state-of-the-art MIP solver, applying it to tasks such as node selection and warm-starting.
  arXiv  Detail & Related papers  (2022-05-27T19:34:14Z)
• A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
  This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors. The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement.
  arXiv  Detail & Related papers  (2021-11-26T06:33:29Z)
• An Online Prediction Approach Based on Incremental Support Vector Machine for Dynamic Multiobjective Optimization [19.336520152294213]
  We propose a novel prediction algorithm based on incremental support vector machine (ISVM) We treat the solving of dynamic multiobjective optimization problems (DMOPs) as an online learning process. The proposed algorithm can effectively tackle dynamic multiobjective optimization problems.
  arXiv  Detail & Related papers  (2021-02-24T08:51:23Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  Decision making under uncertainty is critical to real-world, autonomous systems. Model Predictive Control (MPC) methods have demonstrated favorable performance in practice, but remain limited when dealing with complex distributions. We show that this framework leads to successful planning in challenging, non optimal control problems.
  arXiv  Detail & Related papers  (2020-11-15T22:36:59Z)
• Boosting Ant Colony Optimization via Solution Prediction and Machine Learning [10.687150889251031]
  This paper introduces an enhanced meta-heuristic (ML-ACO) that combines machine learning (ML) and ant colony optimization (ACO) to solve optimization problems.
  arXiv  Detail & Related papers  (2020-07-29T13:03:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.