J. Gondzio, P. P. González-Brevis, P. Munari
Abstract
The primal-dual column generation method (PDCGM) is a general purpose
column generation technique that relies on the primal-dual interior
point method to solve the restricted master problems. The use of this
interior point method variant allows to obtain suboptimal and well-centered
dual solutions which naturally stabilize the column generation.
A reduction in the number of calls to the oracle and in the CPU times
are typically observed when compared to the standard column generation,
which relies on extreme optimal dual solutions. In this paper,
we investigate the behaviour of the PDCGM when solving large-scale
convex optimization problems. We have selected applications that
arise in important real-life contexts such as data analysis
(multiple kernel learning problem), decision-making under uncertainty
(two-stage stochastic programming problems) and telecommunication
and transportation networks (multicommodity network flow problem).
In the numerical experiments, we use publicly available benchmark instances
to compare the performance of the PDCGM against state-of-the-art methods.
The results suggest that the PDCGM offers an attractive alternative over
specialized methods since it remains competitive in terms of number
of iterations and CPU times.
Key words: Column Generation, Cutting Plane Method, Interior Point Methods, Convex Optimization, Multiple Kernel Learning Problem, Two-stage Stochastic Programming, Multicommodity Network Flow Problem