EURO 2025 Leeds
Abstract Submission

1882. Data-Driven Constructive Metaheuristic for Combinatorial Problems

Invited abstract in session MA-38: Automating the Design, Generation and Control of Optimization Algorithms 1, stream Data Science meets Optimization.

Monday, 8:30-10:00
Room: Michael Sadler LG19

Authors (first author is the speaker)

1. Mariusz Kaleta
Inistitute of Control & Computation Engineering, Warsaw University of Technology
2. Tomasz Sliwinski
Institute of Control and Computation Engineering, Warsaw University of Technology

Abstract

We propose a general approach to solving combinatorial optimization problems by leveraging the fact that, in many practical cases, input data exhibit inherent regularities. For example, the parameters of packed items or scheduled tasks often follow specific patterns. Our new metaheuristic applies to problems where solutions can be constructed iteratively, such as sequentially packing items or dispatching operations to a partially built schedule.

At each iteration, a set of candidate decisions is considered and scored using a small-scale simple feed-forward neural network, selecting the decision with the highest score. The network’s low complexity enables an evolutionary strategy for optimizing its parameters, treating the construction algorithm as a black-box optimization problem. In this strategy, the population of individuals represents a set of neural networks, effectively defining a population of constructive algorithms.
The proposed approach is general (“meta-“), requiring the specification of a method for generating candidate decisions, a feature vector describing the current state and potential decisions, and a transformation function that updates the state.

We showcase results for a series of well-known combinatorial problems, including Strip Packing, Cutting Stock, and Flexible Job Shop, demonstrating the superiority of our approach over state-of-the-art constructive algorithms.

Keywords

Status: accepted

Back to the list of papers