Relaxed Dual Optimal Inequalities for Relaxed Columns: with Application to Vehicle Routing

In this paper we accelerate the column generation (CG) solution to expanded linear programming (LP) relaxations (Barnhart et al. 1996) using dual optimal inequalities (Ben Amor et al. 2006) (DOI). Expanded LP relaxations are used to solve integer linear programs (ILPs) for which compact LP relaxations are very loose. In contrast to compact LP relaxations, which contain a small number of variables, expanded LP relaxations contain a massive number of variables (called columns). However an expanded LP relaxation is often much tighter than the corresponding compact LP relaxation, and permits efficient (often in practice exact) optimization (Yarkony et al. 2019) of the corresponding ILP. To solve expanded LP relaxations, CG is used. Since the set of all feasible columns is enormous and can not be easily enumerated, a sufficient set is constructed iteratively using CG. The process of identifying negative reduced cost columns is called pricing.