Local techniques in quadratic optimization and Satisfiability, and their applications

Optimization problems are important from both theoretical and practical points of view. For decades, they have been in the focus of a wide and very active research area. There are studies on designing efficient heuristics and exact algorithms for solving optimization problems, as well as, using them to build practical applications. In many cases that are important for applications finding exact or even approximate solutions is NP-hard. In this thesis, we attempt to design heuristics and algorithms for certain NP-hard optimization problems, analyze those algorithms, evaluate their performance empirically, and look for possible applications. In particular, we focus on incorporating quantum annealing devices into our heuristic methods and applications.We conduct an experimental evaluation on the quantum annealing device built by D-Wave Systems Inc, a Vancouver based startup company. As a new piece of technology which is still under development, there are many open questions related to the current device. The aim of the evaluation is to understand the behaviour and performance of the device on NP-hard optimization problems. The results of our study show that the device performs well on several classes of benchmark problems. Moreover, the evaluation also reveals two pressing issues that limit the practical use of the device. To tackle these issues, we consider the random Max2SAT problem, in which instances are 2CNFs with a fixed clause-to-variables ratio, drawn at random according to some distribution. More precisely, we introduce two distributions of 2CNFs, in both of which instances are drawn from the set of formulas with more than average number of satisfiable clauses. We establish a connection between these two distributions, identify the likely level of satisfiability of a random 2CNF, and evaluate the performance of very basic local heuristics on these distributions. To test the feasibility of local quadratic optimization methods in applications, we consider problems in the domains of social network analysis and recommender systems. We build models for the link sign prediction problem and the rating prediction problem. These models are built using local approximation heuristics. Both models show good prediction accuracy on real-life dataset.