Computing Optimized Path Integrals for Knapsack Feasibility

Endric Daues () and Ulf Friedrich ()
Additional contact information
Endric Daues: Fu Foundation School of Engineering and Applied Science, Columbia University, New York, New York 10027
Ulf Friedrich: Faculty of Mathematics, Otto von Guericke University Magdeburg, 39106 Magdeburg, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2163-2176

Abstract: A generating function technique for solving integer programs via the evaluation of complex path integrals is discussed from a theoretical and computational perspective. Applying the method to knapsack feasibility problems, it is demonstrated how the presented numerical integration algorithm benefits from a preoptimized path of integration. After discussing the algorithmic setup in detail, a numerical study is implemented to evaluate the computational performance of the preoptimized integration method, and the algorithmic parameters are tuned to a set of knapsack instances. The goal is to highlight the method’s computational advantage for hard knapsack instances. Summary of Contribution: A method for evaluating the feasibility of knapsack problems is discussed and connected to the existing theory on generating function techniques for computational integer optimization. Specifically, the number of solutions to knapsack instances is computed using numerical quadrature of complex path integrals. The choice of the path of integration is identified as an important degree of freedom, and it is shown that preoptimizing the path improves the computational performance for hard instances significantly. The scope of this work is to give a self-contained presentation of the mathematical theory, introduce and discuss path optimization as a presolving routine, and demonstrate the computational performance of the overall approach with the help of a detailed numerical study. The main goal is to highlight the computational advantage of the new algorithm for hard knapsack instances.

Keywords: integer programming; Cauchy’s integral formula; path optimization; generating functions; computational study (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1142 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2163-2176

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().