Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces learned pairwise deep dual-optimal inequalities (L-PDDOIs) to enhance the stability of dual solutions in column generation, a critical component in large-scale optimization for vehicle routing problems. By predicting pairwise orderings between dual variables and integrating their primal counterparts, the method effectively reduces convergence time while maintaining solution quality. The results demonstrate a significant reduction in geometric mean root column generation time by up to 93.9% with minimal impact on bound losses, showcasing the method's efficacy in complex routing scenarios.
Achieving up to 93.9% faster convergence in vehicle routing optimization while only sacrificing minimal solution quality is a game changer for large-scale optimization.
Column generation (CG) is central to many large-scale optimization algorithms, including branch-price-and-cut methods for vehicle routing problems, but unstable dual solutions can substantially slow its convergence. Existing deep dual-optimal inequalities can reduce this instability by restricting the dual space. Their construction, however, typically relies on problem-specific exchange arguments that are difficult to establish for routing problems with capacity limits, time windows, and other resource constraints. We introduce learned pairwise deep dual-optimal inequalities (L-PDDOIs), a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem. To construct training labels, the framework samples optimal dual solutions and selects pairwise order relations that hold simultaneously on a sufficiently large common subset of the samples. A classifier then assigns a score to each candidate relation. Because conflicts and redundancies among the predicted relations can impair performance, graph-based postprocessing filters and compresses the candidate set before deployment. We further introduce a recovery procedure that selectively relaxes learned inequalities and provides a certificate when the baseline CG bound has been restored. On the main test sets for the capacitated vehicle routing problem and the vehicle routing problem with time windows, direct deployment of L-PDDOIs reduces the geometric mean root CG time by 89.7% and 93.9%, respectively, while incurring mean bound losses of only 1.3% and 0.5%. The recovery procedure retains corresponding time reductions of 54.8% and 83.1%, respectively, while guaranteeing no loss in the CG bound.