Research Goals

On this page you can find a verbose description of (some of) the long term goals of my research. If you wandered onto this page from the outside and are more interested in a summary of my current research you can check out my publications, the presentations I’ve given or a list of the honors and awards that I’ve received.

My main research interest:

Understanding Difficult Problems through exact solution approaches

Difficult problems are encountered in various different domains. Many interesting problems are provably computationally challenging (NP-hard and beyond). Due to their abundance there have been much effort on coming up with good solution methods to them. During my PhD studies, I worked on developing Maximum Satisfiability as a generic framework for exactly solving NP-hard optimization problems.

Currently it is unknown if fast algorithms exist to NP-hard problems. Personally I lean towards thinking that P \neq NP, i.e. that there does not exist polynomial time solution algorithms to many of the problems that are encountered in industry and academia. This does not however make the study of exact solution methods to such problems irrelevant. NP-hardness is after all, only a worst case guarantee. A problem being NP-hard means that there (probably) does not exist a solution algorithm capable of exactly solving every instance of that problem in polynomial time. One motivation for studying exact methods comes from the fact that “every instance” in this context means “every theoretically possible instance” not “every instance encountered in practical applications”. The distinction is important; in my PhD thesis I used an example of a delivery company wishing to minimize the length of their delivery routes, i.e. solve the traveling salesperson problem (TSP). Every theoretically possible instance of this problem includes a lot of delivery locations that are never encountered in practice, a company based in Helsinki is probably never going to deliver anything to New York as a part of their route. In other words, for this application a solution method to TSP that is able to exactly solve all instances which are encountered by the company in practice is sufficient, even if that solution algorithm would not be efficient on all theoretically possible instances.  This post on Math \cap Programming goes into more detail on this argument using a more entertaining example.

While exact algorithms for NP-hard problems do indeed work well in some applications, my main interest in studying them is a desire to understand what exactly makes some problems complicated. As said, I do not believe P = NP and as such I do not believe that the study of exact solution approaches to NP hard problems will lead to a exact solution algorithm that runs in polynomial time on every instance. Instead I think that developing exact algorithms capable of solving smaller instances, could result in new and deep insights into computational complexity at large. These insights could then be used in the development of approximative and local search algorithms  that can in turn be used to solve instances of industrial sizes.