EUVIMEDEUVIMED entdecken
Crossref

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size

Christoph Hertrich, Martin Skutella

INFORMS Journal on Computing · 2023-09 · 35 (5) · 1079-1097

DOI: 10.1287/ijoc.2021.0225 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2023-09. Verfasst von Christoph Hertrich und 1 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 32 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard knapsack problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum knapsack solution is sufficient to find optimum knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed knapsack solution: for knapsack instances consisting of n items, an RNN of depth five and width w computes a solution of value at least [Formula: see text] times the optimum solution value. Our results build on a classical dynamic programming formulation of the knapsack problem and a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the knapsack problem. A carefully conducted computational study qualitatively supports our theoretical size bounds. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various shortest path problems, the longest common subsequence problem, and the traveling salesperson problem. History: Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. An extended abstract of this article, including Figures 1 – 7 , appeared in the Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, 7685–7693 ( Hertrich and Skutella 2021 ); see https://ojs.aaai.org/index.php/AAAI/article/view/16939 ; copyright © 2021, Association for the Advancement of Artificial Intelligence. Funding: This work was supported by the Deutsche Forschungsgemeinschaft [Grants DFG-GRK 2434 and EXC-2046/1, Project 390685689] and the H2020 European Research Council [ScaleOpt-757481].

Zitieren

APA

Hertrich, C., & Skutella, M. (2023). Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size. INFORMS Journal on Computing, 35(5), 1079-1097. https://doi.org/10.1287/ijoc.2021.0225

Vancouver

Hertrich C, Skutella M. Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size. INFORMS Journal on Computing. 2023;35(5):1079-1097. doi:10.1287/ijoc.2021.0225

BibTeX
@article{Hertrich2023,
  author = {Hertrich, Christoph and Skutella, Martin},
  title = {Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size},
  journal = {INFORMS Journal on Computing},
  year = {2023},
  volume = {35},
  number = {5},
  pages = {1079--1097},
  doi = {10.1287/ijoc.2021.0225}
}
Kostenlos starten →