Optimization Online


A new warmstarting strategy for the primal-dual column generation method

Jacek Gondzio(J.Gondzio***at***ed.ac.uk)
Pablo González-Brevis(P.Gonzalez-Brevis***at***sms.ed.ac.uk)

Abstract: This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts and on a suitable initial point are discussed. Additionally, the strategy ensures that the duality gap of the warmstart is bounded by the old duality gap multiplied with a (small) constant, which depends on the relation between the old and modified problems. Computational experiments demonstrate the gains achieved when compared to a coldstart approach.

Keywords: interior point methods, warmstarting, column generation, linear programming, cutting stock problem

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

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Technical Report ERGO 12-007 University of Edinburgh, School of Mathematics June, 2012

Download: [PDF]

Entry Submitted: 06/24/2012
Entry Accepted: 06/24/2012
Entry Last Modified: 06/24/2012

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 Optimization Society