PDCGM - Primal-Dual Column Generation Method
PDCGM is a package for solving large scale optimization problems
using the primal-dual column generation method.
It has been written by Jacek Gondzio,
P. P. González-Brevis,
and Robert Sarkissian.
PDCGM uses HOPDM
interior point code to solve restricted master problems.
version of PDCGM is available
The distribution version is described in the following paper:
and contains the following example applications:
- small demo version with quadratic programming problems
- capacitated lot-sizing problem with setup times
- cutting stock problem
- multicommodity network flow problem
- multiple kernel learning problem
- two-stage stochastic programming problem
- vehicle routing problem with time windows
The following papers demonstrate mathematical background of the PDCGM
algorithm and report on its successful applications:
An old version of PDCGM was described in:
- J. Gondzio, P. González-Brevis, P. Munari,
New Developments in the Primal-Dual Column Generation Technique,
European Journal of Operational Research 224 (2013) 41-51.
- P. Munari and J. Gondzio,
Using the Primal-Dual Interior Point Algorithm within
the Branch-Price-and-Cut Method,
Computers and Operations Research 40 (2013) No 8, pp. 2026-2036.
- J. Gondzio and P. González-Brevis,
A New Warmstarting Strategy for the Primal-Dual Column Generation Method,
Mathematical Programming A 152 (2015) 113-146.
- J. Gondzio and P. González-Brevis, P. Munari,
Large-Scale Optimization with the Primal-Dual Column Generation Method,
Mathematical Programming Computation 8 (2016) 47-82.
- P. Munari, A. Moreno, J. De La Vega, D. Alem, J. Gondzio and R. Morabito,
The Robust Vehicle Routing Problem with Time Windows:
Compact Formulation and Branch-Price-and-Cut Method,
Transportation Science 53 (2019) No 4, 917-1212.
Published online June 24, 2019.
- J. Gondzio and R. Sarkissian, Column Generation with a Primal-Dual
Method, Logilab Technical Report 96.6, Department of Management Studies,
University of Geneva, Switzerland, June 1996.
TR 96.6 (PDF file).