Reduce-then-Optimize for the Fixed-Charge Transportation Problem

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.