2006/01/01 by Christian Jansson, Jansson, Christian
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Combinatorial Optimization #Constraint Satisfaction and Optimization #Ill-posed Problems #Numerical Methods and Algorithms #Semidefinite Programming #Verification Methods
paper · doi:10.4230/dagsemproc.05391.7
openalex publication_date 2006/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many current deterministic solvers for NP-hard 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 exact solutions can be obtained by rigorously bounding the optimal value of semidefinite relaxations, even in the ill-posed case. All rounding errors due to floating point arithmetic are taken into account.