Ehmes, Sebastian ; Kratz, Maximilian ; Schürr, Andy (2022)
Graph-Based Specification and Automated Construction of ILP Problems.
In: Electronic Proceedings in Theoretical Computer Science, 374
doi: 10.4204/EPTCS.374
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
In the Model-Driven Software Engineering (MDSE) community, the combination of techniques operating on graph-based models (e.g., Pattern Matching (PM) and Graph Transformation (GT)) and Integer Linear Programming (ILP) is a common occurrence, since ILP solvers offer a powerful approach to solve linear optimization problems and help to enforce global constraints while delivering optimal solutions. However, designing and specifying complex optimization problems from more abstract problem descriptions can be a challenging task. A designer must be an expert in the specific problem domain as well as the ILP optimization domain to translate the given problem into a valid ILP problem. Typically, domain-specific ILP problem generators are hand-crafted by experts, to avoid specifying a new ILP problem by hand for each new instance of a problem domain. Unfortunately, the task of writing ILP problem generators is an exercise, which has to be repeated for each new scenario, tool, and approach. For this purpose, we introduce the GIPS (Graph-Based ILP Problem Specification Tool) framework that simplifies the development of ILP problem generators for graph-based optimization problems and a new Domain-Specific Language (DSL) called GIPSL (Graph-Based ILP Problem Specification Language) that integrates GT and ILP problems on an abstract level. Our approach uses GIPSL specifications as a starting point to derive ILP problem generators for a specific application domain automatically. First experiments show that the derived ILP problem generators can compete with hand-crafted programs developed by ILP experts.
Typ des Eintrags: | Artikel |
---|---|
Erschienen: | 2022 |
Autor(en): | Ehmes, Sebastian ; Kratz, Maximilian ; Schürr, Andy |
Art des Eintrags: | Bibliographie |
Titel: | Graph-Based Specification and Automated Construction of ILP Problems |
Sprache: | Englisch |
Publikationsjahr: | 22 Dezember 2022 |
Verlag: | Open Publishing Association |
Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Electronic Proceedings in Theoretical Computer Science |
Jahrgang/Volume einer Zeitschrift: | 374 |
DOI: | 10.4204/EPTCS.374 |
URL / URN: | https://cgi.cse.unsw.edu.au/~eptcs/content.cgi?GCM2022 |
Zugehörige Links: | |
Kurzbeschreibung (Abstract): | In the Model-Driven Software Engineering (MDSE) community, the combination of techniques operating on graph-based models (e.g., Pattern Matching (PM) and Graph Transformation (GT)) and Integer Linear Programming (ILP) is a common occurrence, since ILP solvers offer a powerful approach to solve linear optimization problems and help to enforce global constraints while delivering optimal solutions. However, designing and specifying complex optimization problems from more abstract problem descriptions can be a challenging task. A designer must be an expert in the specific problem domain as well as the ILP optimization domain to translate the given problem into a valid ILP problem. Typically, domain-specific ILP problem generators are hand-crafted by experts, to avoid specifying a new ILP problem by hand for each new instance of a problem domain. Unfortunately, the task of writing ILP problem generators is an exercise, which has to be repeated for each new scenario, tool, and approach. For this purpose, we introduce the GIPS (Graph-Based ILP Problem Specification Tool) framework that simplifies the development of ILP problem generators for graph-based optimization problems and a new Domain-Specific Language (DSL) called GIPSL (Graph-Based ILP Problem Specification Language) that integrates GT and ILP problems on an abstract level. Our approach uses GIPSL specifications as a starting point to derive ILP problem generators for a specific application domain automatically. First experiments show that the derived ILP problem generators can compete with hand-crafted programs developed by ILP experts. |
Zusätzliche Informationen: | This volume contains the post-proceedings of the 13th International Workshop on Graph Computation Models (GCM 2022), which was held in Nantes, France on 6th July 2022 as part of the Software Technologies: Applications and Foundations Conference (STAF 2022). |
Fachbereich(e)/-gebiet(e): | 18 Fachbereich Elektrotechnik und Informationstechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Echtzeitsysteme 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > A: Konstruktionsmethodik DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > A: Konstruktionsmethodik > Teilprojekt A1: Modellierung |
Hinterlegungsdatum: | 02 Jan 2023 08:43 |
Letzte Änderung: | 11 Mai 2023 09:53 |
PPN: | |
Export: | |
Suche nach Titel in: | TUfind oder in Google |
![]() |
Frage zum Eintrag |
Optionen (nur für Redakteure)
![]() |
Redaktionelle Details anzeigen |