Optimization Online


Solving IP via Complex Integration on Shortest Paths

Ulf Friedrich(ulf.friedrich***at***tum.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 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.

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
Entry Accepted: 06/19/2020
Entry Last Modified: 06/19/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