Using the weighted geometric series expansion, it is shown how integer programming can be solved by evaluating complex path integrals based on a multi-path version of Cauchy’s integral formula. In contrast to existing generating function approaches, the algorithm relies only on complex quadrature and no algebraic techniques are needed. In view of fast implementations of the method, it is demonstrated how preprocessing the path of integration improves the condition number of the quadrature problem. An algorithm that uses the shortest path of integration is discussed and illustrated by computing feasibility instances of knapsack problems.
Citation
Technical University of Munich, Operations Research, Arcisstr. 21, 80333 Munich, Germany