GIPS: A Graph- and MILP-based Optimization Framework

The ever-increasing complexity of modern software systems poses significant challenges for efficient and effective software development. As software systems grow in size and functionality, traditional development methodologies struggle to manage the resulting intricacies. While existing approaches such as Integrated Development Environments (IDEs), version control systems, and AI-based assistants focus primarily on programming and maintenance, Model-driven Engineering (MDE) aims to address this complexity holistically. By leveraging models at various abstraction levels, MDE simplifies communication, enhances documentation, and provides frameworks for the design, optimization, and evolution of software systems. Model-driven Software Development (MDSD) goes beyond that and assigns to models a fundamental and driving role throughout the software development process. In MDSD, models are not only used for planning and documentation purposes, but also serve as central artifacts for generating, adapting, and maintaining software systems.

This thesis contributes to the growing field of MDSD by addressing challenges in model repair, optimization, and synchronization. These challenges often share common requirements: defining constraints, optimizing objectives, and applying model transformations effectively. However, the repeated manual implementation and integration of these techniques across different domains introduces redundancy, inefficiency, and error potential. To overcome these challenges, we present Graph-based (M)ILP Problem Specification (GIPS), a generic framework combining Pattern Matching (PM), Graph Transformation (GT), and Mixed Integer Linear Programming (MILP). At the core of GIPS lies the Graph-based (M)ILP Problem Specification Language (GIPSL), which enables the integrated specification of graph patterns, GT rules, (global) constraints, and an objective function. Along with an input model, GIPS generates an MILP problem from a GIPSL specification, solves it using off-the-shelf solvers (e.g., GUROBI), and uses the solution to modify the input model with GT rules, such that it adheres to the defined constraints and optimizes the objective function.

This work demonstrates how a unified, generic framework drastically reduces the development effort for approaches revolving around optimization and transformation problems in MDSD, paving the way for more efficient and automated model-based software development. Furthermore, we show that our approach not only simplifies the development process but also performs on par with handwritten and domain-specific solutions in terms of runtime performance. In addition, we demonstrate that the combination of PM and MILP can drastically reduce the runtime of the problem-solving phase without significantly impacting the overall runtime (including PM and MILP problem generation sub-tasks).

Die ständig wachsende Komplexität moderner Softwaresysteme stellt erhebliche Herausforderungen für eine effiziente und effektive Softwareentwicklung dar. Mit zunehmender Größe und wachsender Funktionalität von Softwaresystemen stoßen traditionelle Entwicklungsmethoden an ihre Grenzen, wenn es darum geht, die resultierende Komplexität zu bewältigen. Während bestehende Werkzeuge und Paradigmen wie Integrierte Entwicklungsumgebungen (IDEs), Versionskontrollsysteme und KI-gestützte Assistenten hauptsächlich auf Programmierung und Wartung fokussiert sind, zielt der Ansatz der modellgetriebenen Entwicklung (MDE) darauf ab, die Herausforderungen durch die wachsende Komplexität der Projekte ganzheitlich zu adressieren. Durch die Nutzung von Modellen auf verschiedenen Abstraktionsebenen vereinfacht MDE die Kommunikation, verbessert die Dokumentation und schafft Rahmenbedingungen für das Design, die Optimierung und die Weiterentwicklung von Softwaresystemen. Die modellgetriebene Softwareentwicklung (MDSD), als Teildisziplin von MDE, geht noch einen Schritt weiter und weist Modellen eine tragende und zentrale Rolle im gesamten Softwareentwicklungsprozess zu. In MDSD dienen Modelle nicht nur der Planung und Dokumentation, sondern fungieren als zentrale Artefakte zur Generierung, Anpassung und Wartung von Softwaresystemen. Diese Arbeit leistet einen Beitrag zur wachsenden Forschungslandschaft der MDSD, indem sie Herausforderungen in den Bereichen Modellreparatur, Modelloptimierung und Modellsynchronisation adressiert. Diese Problemstellungen haben oft gemeinsame Herausforderungen: die Definition von Randbedingungen, die Optimierung von Zielfunktionen und die gezielte Anwendung von Modelltransformationen. Allerdings führt die wiederholte manuelle Implementierung und Integration solcher Techniken in verschiedenen Domänen zu Redundanz, Ineffizienz und einer erhöhten Fehleranfälligkeit. Um diese Herausforderungen zu bewältigen, präsentieren wir das GIPS-Framework (Graph-based MILP Problem Specification Framework), eine generische Lösung, die Pattern Matching (PM), Graphtransformationen (GT) und ganzzahlig lineare Programmierung (MILP) kombiniert. Im Kern von GIPS steht die GIPSL-Spezifikationssprache (Graph-based MILP Problem Specification Language), die die Definition von Graphmustern, GT-Regeln, globalen Randbedingungen und einer Zielfunktion ermöglicht. Basierend auf einer GIPSL-Spezifikation und einem Eingabemodell generiert GIPS ein MILP-Problem, löst es mit Standard-Solvern (z.B. GUROBI) und modifiziert das Eingabemodell mithilfe von GT-Regeln, sodass es den definierten Randbedingungen entspricht und die Zielfunktion optimiert. Diese Arbeit zeigt, wie ein einheitliches, generisches Framework den Entwicklungsaufwand für Optimierungs- und Transformationsprobleme in der MDSD stark reduziert und so den Weg für eine effizientere und stärker automatisierte modellbasierte Softwareentwicklung ebnet. Darüber hinaus demonstrieren wir, dass unser Ansatz nicht nur die Entwicklung vereinfacht, sondern auch in Bezug auf die Laufzeitperformance mit handgeschriebenen und domänenspezifischen Lösungen mithalten kann. Zudem zeigen wir, dass die Kombination aus PM und MILP die Laufzeit der Problemlösungsphase erheblich reduzieren kann, ohne großen Einfluss auf die Gesamtlaufzeit (inklusive PM- und Problemgenerierungslaufzeit) zu haben.