Automatic Generation of Combinatorial Reoptimisation Problem Specifications: A Vision

• URL: http://arxiv.org/abs/2510.02002v1
• Date: Thu, 02 Oct 2025 13:23:52 GMT
• Title: Automatic Generation of Combinatorial Reoptimisation Problem Specifications: A Vision
• Authors: Maximilian Kratz, Steffen Zschaler, Jens Kosiol, Gabriele Taentzer,
• Abstract summary: We argue that Model-Driven Engineering (MDE) offers new opportunities for the systematic derivation of reoptimisation problems.<n>We focus on reoptimisation problems and provide an initial categorisation of changing problems and strategies for deriving the corresponding reoptimisation specifications.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Once an optimisation problem has been solved, the solution may need adaptation when contextual factors change. This challenge, also known as reoptimisation, has been addressed in various problem domains, such as railway crew rescheduling, nurse rerostering, or aircraft recovery. This requires a modified problem to be solved again to ensure that the adapted solution is optimal in the new context. However, the new optimisation problem differs notably from the original problem: (i) we want to make only minimal changes to the original solution to minimise the impact; (ii) we may be unable to change some parts of the original solution (e.g., because they refer to past allocations); and (iii) we need to derive a change script from the original solution to the new solution. In this paper, we argue that Model-Driven Engineering (MDE) - in particular, the use of declarative modelling languages and model transformations for the high-level specification of optimisation problems - offers new opportunities for the systematic derivation of reoptimisation problems from the original optimisation problem specification. We focus on combinatorial reoptimisation problems and provide an initial categorisation of changing problems and strategies for deriving the corresponding reoptimisation specifications. We introduce an initial proof-of-concept implementation based on the GIPS (Graph-Based (Mixed) Integer Linear Programming Problem Specification) tool and apply it to an example resource-allocation problem: the allocation of teaching assistants to teaching sessions.

Related papers

• 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.<n>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.<n>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)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Learning Adaptive Evolutionary Computation for Solving Multi-Objective Optimization Problems [3.3266268089678257]
  This paper proposes a framework that integrates MOEAs with adaptive parameter control using Deep Reinforcement Learning (DRL) The DRL policy is trained to adaptively set the values that dictate the intensity and probability of mutation for solutions during optimization. We show the learned policy is transferable, i.e., the policy trained on a simple benchmark problem can be directly applied to solve the complex warehouse optimization problem.
  arXiv  Detail & Related papers  (2022-11-01T22:08:34Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs.
  arXiv  Detail & Related papers  (2021-02-14T18:05:42Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  We propose a novel solution for challenging non-problems of multiple variables. Our proposed approach is able to achieve effective iterations in cases while other methods would typically fail.
  arXiv  Detail & Related papers  (2020-09-09T10:45:00Z)
• Differentially Private Convex Optimization with Feasibility Guarantees [44.36831037077509]
  This paper develops a novel differentially private framework to solve convex optimization problems. The proposed framework provides a trade-off between the expected optimality loss and the variance of optimization results.
  arXiv  Detail & Related papers  (2020-06-22T15:30:52Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11:54Z)
• A Permutation-Equivariant Neural Network Architecture For Auction Design [49.41561446069114]
  Design of an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design. In this work, we consider auction design problems that have permutationequivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutationequi optimal mechanism.
  arXiv  Detail & Related papers  (2020-03-02T00:37:36Z)

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.