Graph-Based Specification and Automated Construction of ILP Problems

• URL: http://arxiv.org/abs/2212.11629v2
• Date: Wed, 15 May 2024 14:28:38 GMT
• Title: Graph-Based Specification and Automated Construction of ILP Problems
• Authors: Sebastian Ehmes, Maximilian Kratz, Andy Schürr,
• Abstract summary: We introduce the GIPS (Graph-Based ILP Problem Specification Tool) framework that simplifies the development of ILP problem generators. 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Executable Functional Abstractions: Inferring Generative Programs for Advanced Math Problems [61.26070215983157]
  We introduce the term EFA (Executable Functional Abstraction) to denote such programs for math problems. EFA-like constructs have been shown to be useful for math reasoning as problem generators for stress-testing models. We explore the automatic construction of EFAs for advanced math problems.
  arXiv  Detail & Related papers  (2025-04-14T00:06:48Z)
• EHOP: A Dataset of Everyday NP-Hard Optimization Problems [66.41749917354159]
  Everyday Hard Optimization Problems (EHOP) is a collection of NP-hard optimization problems expressed in natural language. EHOP includes problem formulations that could be found in computer science textbooks, versions that are dressed up as problems that could arise in real life, and variants of well-known problems with inverted rules. We find that state-of-the-art LLMs, across multiple prompting strategies, systematically solve textbook problems more accurately than their real-life and inverted counterparts.
  arXiv  Detail & Related papers  (2025-02-19T14:39:59Z)
• A Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems [0.0]
  In Production Scheduling, the Flexible Job Shop Scheduling Problem (FJSSP) aims to optimize a sequence of operations and assign each to an eligible machine with varying processing times. The resulting problem is called Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W) This paper presents a collection of 402 commonly accepted FJSSP instances and proposes an approach to extend these with worker flexibility.
  arXiv  Detail & Related papers  (2025-01-27T15:56:12Z)
• AutoG: Towards automatic graph construction from tabular data [60.877867570524884]
  We aim to formalize the graph construction problem and propose an effective solution. Existing automatic construction methods can only be applied to some specific cases. We present a set of datasets to formalize and evaluate graph construction methods. Second, we propose an LLM-based solution, AutoG, automatically generating high-quality graph schemas.
  arXiv  Detail & Related papers  (2025-01-25T17:31:56Z)
• Evolving Generalizable Parallel Algorithm Portfolios via Domain-Agnostic Instance Generation [27.138566940625385]
  Generalization is the core objective when trainings from data. Co-evolutionary approaches address this challenge by simultaneously evolving a parallel algorithm portfolio (PAP) and an instance population. This work proposes a general-purpose, off-the-shelf PAP construction approach, named domain-agnostic co-evolution of parameterized search (DACE)
  arXiv  Detail & Related papers  (2025-01-06T10:29:48Z)
• Knowledge Graph Modeling-Driven Large Language Model Operating System (LLM OS) for Task Automation in Process Engineering Problem-Solving [0.0]
  We present the Process Engineering Operations Assistant (PEOA), an AI-driven framework designed to solve complex problems in the chemical and process industries. The framework employs a modular architecture orchestrated by a meta-agent, which serves as the central coordinator. The results demonstrate the framework effectiveness in automating calculations, accelerating prototyping, and providing AI-augmented decision support for industrial processes.
  arXiv  Detail & Related papers  (2024-08-23T13:52:47Z)
• G-LLaVA: Solving Geometric Problem with Multi-Modal Large Language Model [124.68242155098189]
  Large language models (LLMs) have shown remarkable proficiency in human-level reasoning and generation capabilities. G-LLaVA demonstrates exceptional performance in solving geometric problems, significantly outperforming GPT-4-V on the MathVista benchmark with only 7B parameters.
  arXiv  Detail & Related papers  (2023-12-18T17:36:20Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
  We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models. TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one. TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
  arXiv  Detail & Related papers  (2023-10-06T01:40:09Z)
• NeSIG: A Neuro-Symbolic Method for Learning to Generate Planning Problems [9.176056742068814]
  We propose Ne SIG, to the best of our knowledge, the first domain-independent method for automatically generating planning problems. We formulate problem generation as a Markov Decision Process and train two generative policies with Deep Reinforcement Learning to generate problems. Results show Ne SIG is able to automatically generate valid and diverse problems of much greater difficulty than domain-specific generators.
  arXiv  Detail & Related papers  (2023-01-24T19:37:59Z)
• Unsupervised Optimal Power Flow Using Graph Neural Networks [172.33624307594158]
  We use a graph neural network to learn a nonlinear parametrization between the power demanded and the corresponding allocation. We show through simulations that the use of GNNs in this unsupervised learning context leads to solutions comparable to standard solvers.
  arXiv  Detail & Related papers  (2022-10-17T17:30:09Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• GeoQA: A Geometric Question Answering Benchmark Towards Multimodal Numerical Reasoning [172.36214872466707]
  We focus on solving geometric problems, which requires a comprehensive understanding of textual descriptions, visual diagrams, and theorem knowledge. We propose a Geometric Question Answering dataset GeoQA, containing 5,010 geometric problems with corresponding annotated programs.
  arXiv  Detail & Related papers  (2021-05-30T12:34:17Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Exploring Instance Generation for Automated Planning [1.6735240552964108]
  Constraint programming and automated planning are examples of these areas. The efficiency of each solving method varies not only between problems, but also between instances of the same problem. We propose a new approach where the whole planning problem description is modelled using Essence.
  arXiv  Detail & Related papers  (2020-09-21T19:58:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.