A carregar...
Publicação
Benders decomposition in forest road network optimization
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 507.42 KB | Adobe PDF |
Orientador(es)
Resumo(s)
This work focuses on solving a variant of the Multiperiod Fixed Charge Minimum Cost Flow through the Benders Decomposition Approach. Due to the Classical Benders Algorithm being a subpar optimization method, much of the work deals with enhancements that try to make it a viable optimization method, in our case we chose to use Cplex as a benchmark. We ended up proposing three Benders Decomposition Algorithms. All of them are implemented in Cplex and all of them are Branch-and-Benders-Cut, made possible through the use of callbacks. What is more, the three of them also start with a solution to the Linear Relaxation to the Restricted Master Problem inspired by the In-Out method. Finally they also share a Linear Program to extract feasibility cuts that is problem agnostic. The main difference lies in optimality cut selection. We compare the two linear problem classical pareto optimality cut selection against a method inspired by the In-Out method which also produces pareto optimal cuts and does so with a single Linear Program. We were not capable of definetly beating the classical approach although we leave suggestions for future research. The only implementation to systematically beat Cplex uses the classical selection criterion for optimality cuts but as soon as a Master Problem feasible solution is found, a Proximity Search Routine is used to improve upon it, which when it ends provides Branch-and-Benders-Cut with a stronger upper bound before branching.
Descrição
Tese de Mestrado, Estatística e Investigação Operacional, 2025, Universidade de Lisboa, Faculdade de Ciências
Palavras-chave
Multiperiod Fixed Charge Minimum Cost Flow Benders Decomposition Enhancements to the Benders Algorithm