  We address the problem of accelerating column generation (CG) for
set-covering formulations via dual optimal inequalities (DOI). DOI use
knowledge of the dual solution space to derive inequalities that might be
violated by intermediate solutions to a restricted master problem, and as such
are efficient at reducing the number of iterations and the oscillations of the
dual variables commonly observed in column generation procedures. We study two
novel classes of DOI which are referred to as Flexible DOI (F-DOI) and
Smooth-DOI (S-DOI), respectively (and jointly as SF-DOI). F-DOI provide rebates
for covering items more than necessary. S-DOI describe the payment of a penalty
to permit the under-coverage of items in exchange for the over-inclusion of
other items. Unlike other classes of DOI from the literature, the S-DOI and
F-DOI rely on very little to no problem-specific knowledge, and as such have
the potential to be applied to a vast number of problem domains. In particular,
we illustrate the efficiency of the new inequalities by embedding them within a
column generation solver for the single source capacitated facility location
problem (SSCFLP). A speed-up of a factor of up to 130x can be observed as when
compared to a non-stabilized variant of the same CG procedure to achieve the
linear relaxation lower bound on problems with dense columns and structured
assignments costs.
