Summary
International Symposium on Nonlinear Theory and its Applications
2005
Session Number:1-3-1
Session:
Number:1-3-1-1
On Verified Computation in Combinatorial Optimization
Christian Jansson,
pp.714-717
Publication Date:2005/10/18
Online ISSN:2188-5079
Summary:
Many current deterministic solvers for NPhard combinatorial optimization problems are based on nonlinear relaxation techniques that use floating point arithmetic. Occasionally, due to solving these relaxations, rounding errors may produce erroneous results, although the deterministic algorithm should compute the exact solution in a finite number of steps. This may occur especially if the relaxations are ill-conditioned or ill-posed, and if Slater’s constraint qualifications fail. We show how verified results can be obtained by rigorously bounding the optimal value of nonlinear semidefinite relaxations, even in the ill-posed case. All rounding errors due to floating point arithmetic are taken into account.