ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Chebyshev Center Based Column Generation
Cited 8 time in scopus Download 2 time Share share facebook twitter linkedin kakaostory
저자
이충목, 박성수
발행일
201112
출처
Discrete Applied Mathematics, v.159 no.18, pp.2251-2265
ISSN
0166-218X
출판사
Elsevier
DOI
https://dx.doi.org/10.1016/j.dam.2011.08.009
협약과제
11MC1400, SMART Post 구축 기술 개발, 박종흥
초록
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.
키워드
Binpacking problem, Chebyshev center, Generalized assignment problem, Stabilized column generation, Vehicle routing problem
KSP 제안 키워드
Generalized Assignment Problem(GAP), Linear program, Novel algorithm, Numerical experiments, Slow convergence, Vehicle Routing Problem with Time Windows, acceleration techniques, column generation, computational results