Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
Abstract
Arc flow formulations derived from dynamic programs have been used to solve many hard combinatorial optimization problems. They generally have strong linear relaxations, but they may contain a pseudo-polynomial or exponential number of arcs, making large instances difficult to solve directly. A classical heuristic approach to address this limitation is to solve a restricted model obtained by removing arcs based on reduced costs or problem-specific information. We propose Sparsity Refinement Anytime (SRA), a generic algorithm that iteratively solves restricted arc flow formulations while progressively adding arcs according to their scores. These scores are computed either from reduced costs alone or by a machine learning (ML) model whose features, including reduced costs, are derived solely from the arc flow formulation and its linear relaxation. The ML model is trained by imitation learning and combines two neural networks, one for arcs with null reduced costs and one for arcs with positive reduced costs, whose outputs are calibrated into a common score. To reduce the risk of infeasibility of highly restricted problems, SRA also includes a repair procedure. Experiments on the parallel machine total weighted tardiness scheduling problem and the cutting stock problem compare ML-guided and reduced-cost-guided SRA with the direct solution of the complete formulation. SRA improves on the direct solution within the same time limit, substantially for the scheduling problem. ML-guided SRA outperforms reduced-cost-guided SRA on all tested instance sizes, including sizes larger than those used for training.
Related
- EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
- Combinatorial Optimization Augmented Machine Learning for Dynamic Electric Autonomous Dial-a-Ride Problem
- Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
- An Improved Escape Algorithm with Reinforcement Learning and Multi-Strategy Synergy for Global Optimization and Real Problems
- Combinatorial slicing problems of polytopes: How (not) to reconstruct a polytope from its slices
BibTeX
@misc{yan2026generic,
title = {{Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems}},
author = {Fulin Yan and François Clautiaux and Aurélien Froger},
howpublished = {HAL},
year = {2026},
month = oct,
url = {https://hal.science/hal-05836617v1},
note = {CC BY-NC 4.0},
}
RIS
TY - UNPB
TI - Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
AU - Fulin Yan
AU - François Clautiaux
AU - Aurélien Froger
PY - 2026
DA - 2026/10/23
PB - HAL
UR - https://hal.science/hal-05836617v1
AB - Arc flow formulations derived from dynamic programs have been used to solve many hard combinatorial optimization problems. They generally have strong linear relaxations, but they may contain a pseudo-polynomial or exponential number of arcs, making large instances difficult to solve directly. A classical heuristic approach to address this limitation is to solve a restricted model obtained by removing arcs based on reduced costs or problem-specific information. We propose Sparsity Refinement Anytime (SRA), a generic algorithm that iteratively solves restricted arc flow formulations while progressively adding arcs according to their scores. These scores are computed either from reduced costs alone or by a machine learning (ML) model whose features, including reduced costs, are derived solely from the arc flow formulation and its linear relaxation. The ML model is trained by imitation learning and combines two neural networks, one for arcs with null reduced costs and one for arcs with positive reduced costs, whose outputs are calibrated into a common score. To reduce the risk of infeasibility of highly restricted problems, SRA also includes a repair procedure. Experiments on the parallel machine total weighted tardiness scheduling problem and the cutting stock problem compare ML-guided and reduced-cost-guided SRA with the direct solution of the complete formulation. SRA improves on the direct solution within the same time limit, substantially for the scheduling problem. ML-guided SRA outperforms reduced-cost-guided SRA on all tested instance sizes, including sizes larger than those used for training.
ER -