Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems

• URL: http://arxiv.org/abs/2005.05847v2
• Date: Tue, 8 Sep 2020 03:13:18 GMT
• Title: Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems
• Authors: Yuan Sun, Andreas Ernst, Xiaodong Li and Jake Weiner
• Abstract summary: We show that a machine learning model can greedily remove decision variables from an optimization problem that are predicted not to be part of an optimal solution. We consider three scenarios where training and test instances are different in terms of: 1) problem characteristics; 2) problem sizes; and 3) problem types. While the accuracy of predicting unused variables naturally deteriorates as a test instance is further away from the training set, we observe that even when tested on a different TSP problem, the machine learning model still makes useful predictions.
• Score: 5.370742369840518
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization plays an important role in real-world problem solving. In the big data era, the dimensionality of a combinatorial optimization problem is usually very large, which poses a significant challenge to existing solution methods. In this paper, we examine the generalization capability of a machine learning model for problem reduction on the classic travelling salesman problems (TSP). We demonstrate that our method can greedily remove decision variables from an optimization problem that are predicted not to be part of an optimal solution. More specifically, we investigate our model's capability to generalize on test instances that have not been seen during the training phase. We consider three scenarios where training and test instances are different in terms of: 1) problem characteristics; 2) problem sizes; and 3) problem types. Our experiments show that this machine learning based technique can generalize reasonably well over a wide range of TSP test instances with different characteristics or sizes. While the accuracy of predicting unused variables naturally deteriorates as a test instance is further away from the training set, we observe that even when tested on a different TSP problem variant, the machine learning model still makes useful predictions about which variables can be eliminated without significantly impacting solution quality.

Related papers

• Neural Collapse Terminus: A Unified Solution for Class Incremental Learning and Its Variants [166.916517335816]
  In this paper, we offer a unified solution to the misalignment dilemma in the three tasks. We propose neural collapse terminus that is a fixed structure with the maximal equiangular inter-class separation for the whole label space. Our method holds the neural collapse optimality in an incremental fashion regardless of data imbalance or data scarcity.
  arXiv  Detail & Related papers  (2023-08-03T13:09:59Z)
• Ensemble Methods for Robust Support Vector Machines using Integer Programming [0.0]
  We study binary classification problems where we assume that our training data is subject to uncertainty. To tackle this issue in the field of robust machine learning the aim is to develop models which are robust against small perturbations in the training data.
  arXiv  Detail & Related papers  (2022-03-03T10:03:54Z)
• CMW-Net: Learning a Class-Aware Sample Weighting Mapping for Robust Deep Learning [55.733193075728096]
  Modern deep neural networks can easily overfit to biased training data containing corrupted labels or class imbalance. Sample re-weighting methods are popularly used to alleviate this data bias issue. We propose a meta-model capable of adaptively learning an explicit weighting scheme directly from data.
  arXiv  Detail & Related papers  (2022-02-11T13:49:51Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• Characterizing possible failure modes in physics-informed neural networks [55.83255669840384]
  Recent work in scientific machine learning has developed so-called physics-informed neural network (PINN) models. We demonstrate that, while existing PINN methodologies can learn good models for relatively trivial problems, they can easily fail to learn relevant physical phenomena even for simple PDEs. We show that these possible failure modes are not due to the lack of expressivity in the NN architecture, but that the PINN's setup makes the loss landscape very hard to optimize.
  arXiv  Detail & Related papers  (2021-09-02T16:06:45Z)
• Learning Hard Optimization Problems: A Data Generation Perspective [44.4747903763245]
  This paper demonstrates the volatility of the training data to the ability to approximate it. It proposes a method for producing (exact or approximate) solutions to optimization problems that are amenable to supervised tasks.
  arXiv  Detail & Related papers  (2021-06-04T17:03:44Z)
• How to effectively use machine learning models to predict the solutions for optimization problems: lessons from loss function [0.0]
  This paper aims to predict a good solution for constraint optimization problems using advanced machine learning techniques. It extends the work of citeabbasi 2020predicting to use machine learning models for predicting the solution of large-scaled optimization models.
  arXiv  Detail & Related papers  (2021-05-14T02:14:00Z)
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters [10.279748604797911]
  Key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to cope with these challenges. In this thesis, we deal with each of these sources of difficulty in a different way. To efficiently address the big data issue, we develop new methods which in each iteration examine a small random subset of the training data only. To handle the big model issue, we develop methods which in each iteration update
  arXiv  Detail & Related papers  (2020-08-26T21:15:18Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11:54Z)
• Total Deep Variation for Linear Inverse Problems [71.90933869570914]
  We propose a novel learnable general-purpose regularizer exploiting recent architectural design patterns from deep learning. We show state-of-the-art performance for classical image restoration and medical image reconstruction problems.
  arXiv  Detail & Related papers  (2020-01-14T19:01:50Z)

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.