IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i4p2163-2176.html
   My bibliography  Save this article

Computing Optimized Path Integrals for Knapsack Feasibility

Author

Listed:
  • 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)

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.

Suggested Citation

  • Endric Daues & Ulf Friedrich, 2022. "Computing Optimized Path Integrals for Knapsack Feasibility," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2163-2176, July.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2163-2176
    DOI: 10.1287/ijoc.2021.1142
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1142
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2021.1142?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hiroshi Hirai & Ryunosuke Oshiro & Ken’ichiro Tanaka, 2020. "Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 455-464, May.
    2. Jean B. Lasserre & Eduardo S. Zeron, 2003. "On Counting Integral Points in a Convex Rational Polytope," Mathematics of Operations Research, INFORMS, vol. 28(4), pages 853-870, November.
    3. KOEPPE, Matthias & LOUVEAUX, Quentin & WEISMANTEL, Robert & WOLSEY, Laurence A., 2004. "Extended formulations for Gomory corner polyhedra," LIDAM Reprints CORE 1728, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hiroshi Hirai & Ryunosuke Oshiro & Ken’ichiro Tanaka, 2020. "Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 455-464, May.
    2. Jean B. Lasserre & Eduardo S. Zeron, 2005. "An Alternative Algorithm for Counting Lattice Points in a Convex Polytope," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 597-614, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2163-2176. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.