The Toronto Intelligent Decision Engineering Laboratory
people / Dave Yoon

Master of Applied Science in Industrial Engineering (University of Toronto) 2006
Bachelor of Applied Science in Mechanical Engineering with Mechatronics Option (University of Waterloo, 2004)

Masters Thesis

Empirical Analysis of Local Search Algorithms and Problem Difficulty in Satisfiability

Research Interests

My research interest is in local search algorithms for combinatorial optimization. In particular, the behaviour of these algorithms in various problem domains such as satisfiability (SAT) and job-shop scheduling problems. One of the most popular local search algorithms in SAT is Walksat, developed by Bart Selman and Henry Kautz. Although it has been around for more than a decade and serves as a basis for other more complex local search algorithms of today, we still do not have a very good idea of why it works so well. Characterizing the algorithm with respect to the type of path it takes around the search space and its performance around the critically constrained region are some of the things I have done.

I also have done some work on applying various meta-heuristics on local search algorithms for SAT. Path-relinking is an idea from tabu search that has to do with keeping a pool of near-optimal, elite solutions and taking advantage of the information they provide to find an optimal solution. It has shown some promises in certain domains of SAT.

Although SAT is primarily used in theoretical context in the area of Artificial Intelligence and Computer Science, it has merits in applications as well. For example, it maps very well as graph colouring problems and planning problems, and has been shown that SAT-based algorithms are competitive in performance when compared to Constraint Programming based methods. I've had chance to work on applications of SAT in Sandia National Laboratories in New Mexico last summer. The problem was to minimize the public's health risk from contaminated water given a limited number of sensors that can detect contamination in the water network. The problem also maps nicely as SAT, since most variables are binary. However, non-binary variable constraints had to be formulated using Dynamic programming, which greatly inflated the size of the problem. In the end, the SAT algorithm did not perform as well as Integer programming or Set-cover heuristic methods. However, it did present a possible lead for a new research in terms of applications of SAT.

Contact Information

Dave Tae Shik Yoon

University of Toronto Mechanical and Information Engineering