ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Chebyshev Center Based Column Generation
Cited 11 time in scopus Download 3 time Share share facebook twitter linkedin kakaostory
Authors
Chungmok Lee, Sungsoo Park
Issue Date
2011-12
Citation
Discrete Applied Mathematics, v.159, no.18, pp.2251-2265
ISSN
0166-218X
Publisher
Elsevier
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1016/j.dam.2011.08.009
Project Code
11MC1400, Development of Implementation Technology for SMART Post, Jong Heung Park
Abstract
The classical column generation approach often shows a very slow convergence. Many different acceleration techniques have been proposed recently to improve the convergence. Here, we briefly survey these methods and propose a novel algorithm based on the Chebyshev center of the dual polyhedron. The Chebyshev center can be obtained by solving a linear program; consequently, the proposed method can be applied with small modifications on the classical column generation procedure. We also show that the performance of our algorithm can be enhanced by introducing proximity parameters which enable the position of the Chebyshev center to be adjusted. Numerical experiments are conducted on the binpacking, vehicle routing problem with time windows, and the generalized assignment problem. The computational results of these experiments demonstrate the effectiveness of our proposed method. © 2011 Elsevier B.V. All rights reserved.
KSP Keywords
Generalized Assignment Problem(GAP), Linear program, Novel algorithm, Numerical experiments, Slow convergence, Vehicle Routing Problem with Time Windows, acceleration techniques, column generation, computational results