Optimization Online


Computing Optimized Path Integrals for Knapsack Feasibility

Endric Daues(ed2691***at***columbia.edu)
Ulf Friedrich(ulf.friedrich***at***tum.de)

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 solve knapsack feasibility problems, it is demonstrated how the presented numerical integration algorithm benefits from pre-optimizing the path of integration. After discussing the algorithmic set-up in detail, a numerical study is implemented to evaluate the computational performance of the pre-optimized 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 with large coefficients and high numbers of feasible solutions.

Keywords: Integer Programming, Cauchy's Integral Formula, Path Optimization, Generating Functions, Computational Study.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 06/22/2020
Entry Accepted: 06/22/2020
Entry Last Modified: 06/22/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society