Open AccessSmooth and Flexible Dual Optimal Inequalities
Author(s) -
Naveed Haghani,
Claudio Contardo,
Julian Yarkony
Publication year - 2022
Publication title -
informs journal on optimization
Language(s) - English
Resource type - Journals
eISSN - 2575-1492
pISSN - 2575-1484
DOI - 10.1287/ijoo.2021.0057
Subject(s) - solver , column generation , embedding , set (abstract data type) , dual (grammatical number) , mathematical optimization , relaxation (psychology) , column (typography) , computer science , linear programming , upper and lower bounds , mathematics , artificial intelligence , art , social psychology , psychology , telecommunications , mathematical analysis , literature , frame (networking) , programming language
We address the problem of accelerating column generation (CG) for set-covering formulations via dual optimal inequalities (DOIs). We study two novel classes of DOIs, which are referred to as Flexible DOIs (F-DOIs) and Smooth-DOIs (S-DOIs), respectively (and jointly as SF-DOIs). F-DOIs provide rebates for covering items more than necessary. S-DOIs describe the payment of a penalty to permit the undercoverage of items in exchange for the overinclusion of other items. Unlike other classes of DOIs from the literature, the S-DOIs and F-DOIs rely on very little problem-specific knowledge and, as such, have the potential to be applied to a vast number of problem domains. In particular, we discuss the application of the new DOIs to three relevant problems: the single-source capacitated facility location problem, the capacitated p-median problem, and the capacitated vehicle-routing problem. We provide computational evidence of the strength of the new inequalities by embedding them within a column-generation solver for these problems. Substantial speedups can be observed as when compared with a nonstabilized variant of the same CG procedure to achieve the linear-relaxation lower bound on problems with dense columns and structured assignment costs.