758. Formulations and branch-and-cut algorithms for cycle covers with up to p cycles
Invited abstract in session MD-55: Network Optimization 4, stream Network Optimization.
Monday, 14:30-16:00Room: Liberty 1.09
Authors (first author is the speaker)
| 1. | Francisco Canas
|
| DEIO - Departamento de Estatística e Investigação Operacional / CEMS.UL - Center for Mathematical Studies, Universidade de Lisboa - Faculdade de Ciências | |
| 2. | Luís Gouveia
|
| DEIO - Departamento de Estatística e Investigação Operacional, Universidade de Lisboa - Faculdade de Ciências |
Abstract
Given a positive integer p and a weighted undirected graph G, we study a problem in which the objective is to find a minimum weight set of up to p elementary cycles partitioning the vertices of G. We study several exponential sized formulations including i) edge variables only; ii) edge and depot variables only; iii) edge, depot and node-depot assignment (NDA) variables only; iv) edge, depot, NDA and edge-depot assignment (EDA) variables, some of which are known from existing works on similar problems. Branch-and-cut algorithms based on many of these formulations are proposed, and computational experiments are conducted to compare the performance of the different algorithms. The computational testing reveals that some of the formulations including edge, depot and NDA or EDA variables produce the best initial lower bounds and that the best computational times are obtained with the algorithms based on formulations including edge and depot variables only. The best performing algorithm (in terms of computational times) is capable of solving several instances with up to 442 nodes for different values of p.
Keywords
- Combinatorial Optimization
- Vehicle Routing
- Branch and Cut
Status: accepted
Back to the list of papers