Exact solution of network flow models with strong relaxations

Author(s)

de Lima, Vinicius Loti ; Iori, Manuel ; Miyazawa, Flavio Keidi

• Document type: Journal article
• Source: MATHEMATICAL PROGRAMMING; v. 197, n. 2, p. 34-pg., 2022-03-07.

Abstract

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. (AU)

• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 17/11831-1 - Algorithms and models for cutting and packing problems
• Grantee: Vinícius Loti de Lima
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
• FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants