Institutional Repository UDD

A New Warmstarting Strategy for the Primal-Dual Column Generation Method

Show simple item record

dc.contributor.author Gondzio, J
dc.contributor.author González-Brevis, P
dc.date.accessioned 2016-10-07T22:14:17Z
dc.date.available 2016-10-07T22:14:17Z
dc.date.issued 2015
dc.identifier.citation Mathematical Programming August 2015, Volume 152, Issue 1, pp 113–146
dc.identifier.uri es_CL
dc.identifier.uri http://hdl.handle.net/11447/761
dc.identifier.uri http://dx.doi.org/10.1007/s10107-014-0779-8
dc.description.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. es_CL
dc.format.extent 113-146 es_CL
dc.language.iso en_US es_CL
dc.publisher Springer es_CL
dc.title A New Warmstarting Strategy for the Primal-Dual Column Generation Method es_CL
dc.type Artículo es_CL


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account