Computing Optimized Path Integrals for Knapsack Feasibility
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 )
Entry Submitted: 06/22/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|