On this page you can find a verbose description of the really high level motivation for me to do research. The description is mean to be abstract and hopefully non-technical, feel free to send me an e-mail if you want to discuss specifics.

If you wandered onto this page from the outside and are more interested in a summary of my current research you can instead look at my publications, the presentations I’ve given or a list of the honors and awards that I’ve received.

Understanding difficult problems through exact solution approaches

Difficult problems are encountered in various different domains. Many, if not most 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. After finishing my degree, I have continued in this direction while also diversifying my research into other paradigms and solution approaches.

Currently it is unknown if fast (polynomial time) algorithms exist to NP-hard problems. Personally I lean towards thinking that P NP, i.e. that there does not exist a polynomial time solution algorithm 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 statement about the worst-case. 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 Programming goes into more detail on this argument using a more entertaining example.

In addition to developing exact algorithms that work well on “interesting instances” of NP-hard problems another reason for me to study such methods 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 an exact solution algorithm that runs in polynomial time on every instance. Instead, I think that developing exact algorithms capable of solving the instances encountered in practical applications, could result in new  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. Alternatively, exact solution methods can also be used as part of approximative algorithms, for example by first partitioning the search space and then solving the smaller partitions exactly.