Exact solution of network flow models with strong relaxations

• 成果类型: Article
• 署名作者: de Lima, Vinicius Loti; Iori, Manuel; Miyazawa, Flavio Keidi
• 署名单位: Universidade Estadual de Campinas; Universita di Modena e Reggio Emilia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01785-9
• 发表日期: 2023
• 页码: 813-846
• 关键词: linear-programming approach; vehicle-routing problem; cut-and-price; bin-packing; Column Generation; exact algorithm; bounds; DECOMPOSITION

摘要

We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig-Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and packing problems from the literature. The efficiency of the framework is proved by extensive computational experiments, in which a significant number of open instances could be solved to proven optimality for the first time.