User hints for optimisation processes

Innovative improvements in the area of Human-Computer Interaction and User Interfaces have en-abled intuitive and effective applications for a variety of problems. On the other hand, there has also been the realization that several real-world optimization problems still cannot be totally auto-mated. Very often, user interaction is necessary for refining the optimization problem, managing the computational resources available, or validating or adjusting a computer-generated solution. This thesis investigates how humans can help optimization methods to solve such difficult prob-lems. It presents an interactive framework where users play a dynamic and important role by pro-viding hints. Hints are actions that help to insert domain knowledge, to escape from local minima, to reduce the space of solutions to be explored, or to avoid ambiguity when there is more than one optimal solution. Examples of user hints are adjustments of constraints and of an objective function, focusing automatic methods on a subproblem of higher importance, and manual changes of an ex-isting solution. User hints are given in an intuitive way through a graphical interface. Visualization tools are also included in order to inform about the state of the optimization process. We apply the User Hints framework to three combinatorial optimization problems: Graph Clus-tering, Graph Drawing and Map Labeling. Prototype systems are presented and evaluated for each problem. The results of the study indicate that optimization processes can benefit from human interaction. The main goal of this thesis is to list cases where human interaction is helpful, and provide an ar-chitecture for supporting interactive optimization. Our contributions include the general User Hints framework and particular implementations of it for each optimization problem. We also present a general process, with guidelines, for applying our framework to other optimization problems.