EURO 2025 Leeds
Abstract Submission

3024. Using Column Generation with Neighbourhood Pricing to solve the Generalized Assignment Problem

Invited abstract in session TC-20: Exact algorithms for combinatorial optimization, stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: Esther Simpson 2.11

Authors (first author is the speaker)

1. Basile Blayac
engineering, university of auckland
2. Andrew J Mason
Dept Engineering Science, University of Auckland
3. Andrea Raith
Engineering Science, The University of Auckland

Abstract

In the context of column generation, Neighbourhood Pricing is a novel column pricing strategy that narrows the search for new columns to the neighborhoods of existing ones. Neighbourhood Pricing can be used as a Very Large Scale Neighborhood (VLSN) search matheuristic, where it replaces the standard Pricing problem to only explore neighborhoods of feasible integer solutions. It can also be used in Branch and Price as a pricing heuristic. Our study focuses on the Generalized Assignment Problem (GAP), a well-known and challenging scheduling problem in which tasks must be assigned to a set of heterogeneous agents with capacity constraints, with the goal of minimizing the total assignment cost. We introduce two variants of Neighbourhood Pricing for the GAP problem and develop algorithms to use these efficiently. We evaluate the impact of Neighbourhood Pricing approaches on solving GAP instances at the root node and their integration into heuristic methods, and compare these approaches with existing techniques. Finally, we discuss intriguing aspects of the concept, such as the reduction in "fractionality" of solutions during the column generation process.

Keywords

Status: accepted

Back to the list of papers