Large-scale optimization with the primal-dual column generation method

Autor(es)

Gondzio, Jacek ^[1] ; Gonzalez-Brevis, Pablo ^[2] ; Munari, Pedro ^[3]

Afiliação do(s) autor(es)

^[1] Univ Edinburgh, Sch Math, James Clerk Maxwell Bldg, Kings Bldg, Mayfield Rd, Edinburgh EH9 3JZ, Midlothian - Scotland

^[2] Univ Desarrollo, Sch Engn, Ave Sanhueza 1750, Concepcion 4040418 - Chile

^[3] Univ Fed Sao Carlos, Dept Prod Engn, RodoviaWashington Luis Km 235, BR-13565905 Sao Carlos, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: MATHEMATICAL PROGRAMMING COMPUTATION; v. 8, n. 1, p. 47-82, MAR 2016.
• Citações Web of Science: 7

Resumo

The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation process. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for large-scale optimization problems. (AU)

• Processo FAPESP: 14/50228-0 - Formulations and solution methods for vehicle routing problems with data uncertainty
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 14/00939-8 - Métodos Branch-price-and-cut de pontos interiores para variantes do problema de roteamento de veículos
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular