Column generation is central to many large-scale optimization algorithms, but unstable dual solutions can substantially slow its convergence. We introduce learned pairwise deep dual-optimal inequalities, a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem.
A public modular exact solver for vehicle routing problems.
Despite significant advancements in exact methods for vehicle routing problems (VRPs) over the past three decades, there remains a lack of high-performing and accessible open-source solvers for researchers and practitioners. To bridge this gap, we introduce RouteOpt, the first open-source modular exact solver for VRPs, delivering state-of-the-art performance while maintaining a flexible and extensible structure. RouteOpt achieves the best performance reported in the literature on both the capacitated vehicle routing problem (CVRP) and vehicle routing problem with time windows (VRPTW).
Branching is one of the most important components in branch-price-and-cut (BPC) algorithms for solving vehicle routing problems (VRPs) exactly. However, learning to branch is much more challenging in BPC than in branch-and-cut algorithms that are used for solving general mixed integer programs. To address such challenges, we propose the first effective learning-to-branch framework in BPC algorithms, leading to a novel two-stage learning-based branching (2LBB) strategy.
The paper on two-stage learning to branch for exact vehicle routing was accepted by Operations Research.
Presented at the 2024 INFORMS Annual Meeting on modular exact solver design for vehicle routing problems.