EURO 2025 Leeds
Abstract Submission

2895. A subgradient method for the Cubic Facility Layout Problem

Invited abstract in session WC-17: Combinatorial Optimization and Data Processing, stream Combinatorial Optimization.

Wednesday, 12:30-14:00
Room: Esther Simpson 2.08

Authors (first author is the speaker)

1. Thi Thuy An Tran
Michelin
2. Mourad Baiou
CNRS, University Clermont II
3. Rafael Colares
Models and Algorithms to support Decision making, Modelling and Optimization of the Systems
4. Hector Gatt
Michelin

Abstract

This paper addresses a combinatorial optimization problem in automated workshops, where facility arrangements minimize product travel distances. It generalizes the Quadratic Assignment Problem (QAP) introduced by Koopmans and Beckmann (1957).
The QAP involves a one-to-one assignment of facilities to locations to minimize flow-distance costs. Despite its simple definition, it is NP-hard, with instances of 32 locations still unsolved, while the largest optimally solved case has 128 locations.
Our problem extends QAP by introducing unknown flows between facilities. In workshops with replica machines, total flow between machine groups is known, but individual routing decisions add complexity. When all facilities are distinct, it reduces to QAP; otherwise, the objective becomes cubic, defining the Cubic Facility Layout Problem (CFLP).
CFLP groups facilities by type, with capacity constraints and group flows dictating total movement. We solve it using a linearization approach, converting the cubic model into an LP for useful lower bounds. Additionally, we develop a two-stage heuristic that iteratively optimizes layout and flow. Both approaches require solving QAP or CFLP, so we employ the Volume Algorithm, an approximate subgradient method. Since the Volume Algorithm supports parallelization, it can be scaled efficiently for large instances.

Keywords

Status: accepted

Back to the list of papers