Computing Optimized Path Integrals for Knapsack Feasibility

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.

Article

Download

View Computing Optimized Path Integrals for Knapsack Feasibility