Reduce-then-Optimize for the Fixed-Charge Transportation Problem
Caroline Spieckermann (),
Stefan Minner and
Maximilian Schiffer ()
Additional contact information
Caroline Spieckermann: Logistics and Supply Chain Management, TUM School of Management, Technical University of Munich, 80333 Munich, Germany; and Advanced Optimization in a Networked Economy (GRK 2201), Technical University of Munich, 80333 Munich, Germany
Maximilian Schiffer: Munich Data Science Institute, Technical University of Munich, 85748 Garching, Germany; and Business Analytics and Intelligent Systems, TUM School of Management, Technical University of Munich, 80333 Munich, Germany
Transportation Science, 2025, vol. 59, issue 3, 540-564
Abstract:
Research on addressing combinatorial optimization (CO) problems with machine learning (ML) is thriving with a strong focus on replacing exact but slow solvers with faster ML oracles. However, developing accurate and generalizable predictors remains challenging. We investigate a different paradigm, called reduce-then-optimize, that uses ML to reduce the problem complexity for a subsequent CO solver by predicting a relevant subset of variables. We apply this paradigm to the fixed-charge transportation problem (FCTP), an important problem class in logistics and transportation. To obtain a high-quality and problem size-agnostic predictor, we employ a tailored bipartite graph neural network (GNN). We evaluate the performance of our reduce-then-optimize pipeline on various FCTP benchmark data sets to analyze the impact of different instance characteristics, such as the supply-demand ratio or the predominance of the fixed costs, on the problem difficulty and predictability. This includes FCTP variants with edge capacities, fixed-step costs, and blending constraints. The GNN shows good prediction and generalization capabilities that translate into high-quality solutions across all data sets with optimality gaps below 1%, decreasing runtimes of a state-of-the-art mixed-integer linear programming by 80%–95%. When runtimes are limited, the problem reduction provides an effective reduction of the search space, which leads to better solutions in comparison with solving the full problem. Similarly, we systematically improve the solution quality and convergence of two established meta-heuristics by applying our reduce-then-optimize pipeline. As the GNN-based reduce-then-optimize pipeline can be easily adapted to support additional constraints and objectives, it constitutes a flexible and robust solution approach for FCTP solving in practice.
Keywords: fixed-charge transportation problem; problem reduction; machine learning; graph neural networks (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0407 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:59:y:2025:i:3:p:540-564
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().