A graphical environment for creating constraint programming models

Abstract

Viele wichtige Probleme aus der Praxis, etwa das „rotating workforce scheduling problem“ oder das „traveling salesperson problem“ können mit Constraint Programming modelliert werden. Gute Lösungen für diese Probleme können nicht nur große Kostenersparnisse für Firmen ermöglichen, sondern auch die Mitarbeiterzufriedenheit erhöhen. Aus diesem Grund sind in den vergangenen Jahren viele (textbasierte) Constraint Programming Sprachen entstanden. Mit Hilfe dieser Sprachen kann man komplexe Probleme präzise formulieren. Dazu ist es aber nötig, die Syntax der jeweiligen Sprache zu beherrschen. Für viele andere Programmierparadigmen, etwa für objektorientierte Programmierung, wurden graphische Sprachen entwickelt. Für Constraint Programming ist dies unseres Wissens nicht der Fall. Eine graphische Umgebung für Constraint Programming würde es erlauben, wichtige Probleme der Praxis zu modellieren, ohne die Syntax einer textbasierten Sprache zu kennen. Sie könnte auch hilfreich für erfahrene Entwickler sein, wenn sie schnelle und intuitive Modellierung ermöglicht. In dieser Arbeit stellen wir eine neue und intuitive graphische Umgebung zur Erstellung von Constraint Programming Modellen vor. Wir zeigen einen neuen gitterbasierten Ansatz, mit dem es möglich ist, Variablen und Constraints zu erstellen und im zweidimensionalen Raum anzuordnen. Wir zeigen auch Möglichkeiten, häufig vorkommende Subprobleme wie Routen auf eine einfache grapische Art zu modellieren. Wir werden auch demonstrieren, wie solche graphische Modelle in die bekannte MiniZinc Sprache umgewandelt werden können, damit sie mit bestehenden Solvern gelöst werden können. In der Evaluierung haben wir festgestellt, dass es mit der vorgestellten Umgebung möglich ist, viele bekannte Probleme wie das „rotating workforce scheduling problem“, das „social golfer problem“ und das „traveling salesperson problem with time windows“ zu modellieren. In manchen Instanzen haben wir beim Lösen Laufzeiten erreicht, die vergleichbar zu bestehenden Ansätzen sind. Wir haben weiters herausgefunden, dass das Framework am besten für kleinere Instanzen mit niedriger Komplexität geeignet ist, da das Modell dann übersichtlich auf einem Bildschirm dargestellt werden kann. Wir können mögliche Anwendungen im Bereich der Bildung oder für den schnellen Entwurf von Modellen erkennen.

Many practical problems of high importance such as the rotating workforce scheduling problem or the traveling salesperson problem can be modeled with constraint programming. Finding good solutions for those problems can enable great cost reduction for companies and even improve employee satisfaction. Therefore, many powerful text-based constraint programming languages and corresponding solvers have emerged in the previous years. They allow concise formulation of problems but require that the user learns the specific syntax of the language. For other programing paradigms such as object orientated programming, graphical languages have been proposed. To our knowledge, no general purpose graphical constraint programming language exists, that allows modeling without written formulas or constraints. Such a graphical constraint programming environment would not only allow important practical problems to be modeled without having to know the syntax of a text-based language, but could also be helpful to experienced developers if it allows fast and intuitive modeling. In this thesis we propose a new graphical environment for creating constraint programming models. We present a grid-like approach to create variables and constraints and arrange them in the 2D space. We present various possibilities to make constraint programming in this framework as simple and intuitive as possible. We further present ways to model common subproblems in constraint programming, such as routes, in a graphical way. We also demonstrate how graphical models can be translated to the common MiniZinc language, so that they can be solved with existing constraint programming solvers. In the evaluation we have found out that the proposed environment can be successfully used to model a variety of common constraint programming problems such as the rotating workforce scheduling problem, the social golfer problem and the traveling salesperson problem with time windows. In some problem instances, we achieved runtimes that were comparable to existing methods. We have further found out that the framework is best suited for small instances with low complexity, as then the complete model can be displayed on an average computer screen without scrolling. We can see applications for the framework in the field of education, where it can help students learn the concepts of constraint programming.