Back to search

University of British Columbia

Analysing the empirical time complexity of high-performance algorithms for SAT and TSP

Abstract

dc:description

The time complexity of problems and algorithms, i.e., the scaling of the time required for solving a problem instance as a function of instance size, is of key interest in theoretical computer science and practical applications. In this context, the propositional satisfiability (SAT) and the travelling salesperson (TSP) are two of the most intensely studied problems, and it is generally believed that solving SAT or TSP requires exponential time in the worst case. In this work, we refine and extend a recent empirical scaling analysis approach and study the empirical scaling of the running times of several prominent, high-performance SAT and TSP algorithms. For SAT, we focus on random 3-SAT instances from the phase transition region, arguably the most prominent model for difficult SAT instances, and obtain interesting and surprising scaling results for both SLS- and DPLL-based solvers. Particularly, we find solid support for polynomial scaling for SLS-based solvers on phase-transition random 3-SAT instances. We also show that DPLL-based solvers scale exponentially and are faster by only a constant factor in solving satisfiable instances compared to unsatisfiable instances. We further report empirical scaling results for two classes of random 4-SAT instances to gain additional insights into the performance of state-of-the-art SAT solvers. For TSP, we concentrate on two-dimensional random uniform Euclidean (RUE) instances, and characterise the scaling of running time for complete and incomplete algorithms for finding optimal solutions. Our results indicate that the scaling of all these algorithms is consistent with or bounded from above by root-exponential models of the form a·b^(√n). We also explored the impact of automated algorithm configuration on the scaling of these algorithms. Since our approach is applicable beyond SAT and TSP, to enable its broad use, we designed Empirical Scaling Analyser (ESA), an automated tool that can be conveniently used to study empirical scaling of many types of algorithms. In particular, ESA presents scaling analysis results in the form of automatically generated, detailed technical reports. Many results reported in this thesis, including most tables and figures, were automatically generated by ESA and are only slightly modified to fit here.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mu, Zongxu

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 2.5 Canada
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/55351

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mu, Zongxu. Analysing the empirical time complexity of high-performance algorithms for SAT and TSP. master's thesis, University of British Columbia, 2015. http://hdl.handle.net/2429/55351