Effective Profiling of Tree Search in Constraint Programming

Author: 

Maxim Shishmarev

School: 

Faculty of Informaction Technology, Monash University, Australia

Supervisors: 

Guido Tack
Maria Garcia de la Banda
Christopher Mears

Abstract: 

Combinatorial problems, where a set of decisions needs to be made that satisfies a set of constraints and possibly maximises/minimises an objective function, occur frequently in many areas of life, including transportation, emergency management, and energy distribution. Unfortunately, solving these problems is remarkably difficult due to the exponential number of possible sets of decisions that can be made. Modern approaches to solving Combinatorial problems first focus on describing them in a declarative modelling language to form models, and then solving them using general purpose solvers which search among all possible decisions looking for high quality (or optimal) solutions. Constraint Programming is one of the modern solving technologies that underlie these solvers, and it is the focus of this thesis.

How fast a high quality solution can be found by a solver is largely dependent on how the problem is described in the model. For all but the smallest problems, the initial models rarely yield high quality solutions in a reasonable amount of time and need to be modified. In order to know which modifications would be favourable, the modeller needs to determine what parts of the model are responsible for the slow search, modify them, and evaluate the effect of these modification. The above process is traditionally known as profiling.

In imperative (rather than declarative) programming, profiling tools routinely highlight the causes behind inefficiencies in an execution and, in doing so, identify the parts of the program that should be modified. In Constraint Programming, which adheres to the declarative paradigm, such profiling capabilities are not as readily available to the programmer due to its declarative nature, which makes the link between the program and its execution rather tenuous. The existing systems for profiling constraint programs work reasonably well for small problems. However, they lack the means for automatically analysing executions and effectively evaluating model modifications, something crucial when dealing with large real-world problems, when the search for high quality solutions is too long and complex to be analysed manually. Further, many existing systems are solver- dependent and do not support modern solvers and their powerful search techniques.

This work aims to overcome the limitations of the current state of the art by designing an effective profiling system and associated profiling techniques. To achieve this, in this thesis I have designed, implemented and evaluated a profiling system that (a) is efficient and thus scales for large problems, (b) is solver-independent and thus can easily integrate different solvers, and (c) can support modern solvers and be extended to those developed in the future. In addition, I have designed and integrated several profiling techniques into this system: search-tree visualisations that improve on the state of the art, and are more suitable for large problems; a technique for automatically finding recurring patterns in large problems that are often the reason for slow executions and can aid the modeller in improving them; two complimentary techniques that allow modellers to evaluate model modifications; and a technique for analysing so-called learning solvers that can aid the modeller in discovering constraints present in the model that can be strengthened as well as redundant constraints that can be added to the model faster executions for both learning and traditional solvers. Together, these techniques allow modellers to find high quality solutions faster by aiding them in making effective model modifications.

Graduated: 

Monday, April 16, 2018

PDF of thesis: