Optimization Online


New developments in the primal-dual column generation technique

Jacek Gondzio(J.Gondzio***at***ed.ac.uk)
Pablo González-Brevis(P.Gonzalez-Brevis***at***sms.ed.ac.uk)
Pedro Munari(munari***at***icmc.usp.br)

Abstract: The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, we address the primal-dual column generation technique, which relies on well-centred non-optimal solutions of the restricted master problems that are obtained by a primal-dual interior point method. Although good computational results are reported for this technique, it was only applied in a particular class of problems. Moreover, no theoretical analysis to guarantee its convergence is available. Here, we further investigate the primaldual column generation technique and present extensive computational experiments in the context of integer programming, where column generation schemes are widely employed. The results show that the primal-dual technique usually leads to substantial reductions in the number of iterations as well as less running time when compared to the classical and also analytic centre approaches.

Keywords: interior point methods, column generation, linear programming

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Integer Programming

Category 3: Combinatorial Optimization

Citation: School of Mathematics, University of Edinburgh The King's Buildings, Edinburgh, EH9 3JZ, UK Technical Report ERGO 11-001, January 24, 2011.

Download: [PDF]

Entry Submitted: 01/25/2011
Entry Accepted: 01/25/2011
Entry Last Modified: 01/25/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society