  


Solving IP via Complex Integration on Shortest Paths
Ulf Friedrich(ulf.friedrichtum.de) Abstract: Using the weighted geometric series expansion, it is shown how integer programming can be solved by evaluating complex path integrals based on a multipath 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. Keywords: Integer Programming, Generating Function, Cauchy's Integral Formula, Shortest Path of Integration Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Technical University of Munich, Operations Research, Arcisstr. 21, 80333 Munich, Germany Download: [PDF] Entry Submitted: 06/19/2020 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  