CMP events

Jindriska Deckerova presents Robotics RG

On 2021-11-19 09:00 at KN:E-128
Dear colleagues,
let me invite you to the next robotics RG, which takes place on Friday (19.11)
at 9:00 in KN:E-128.

Kobeaga, Gorka & Merino, MarĂ­a & Lozano, Jose. (2020). A revisited
branch-and-cut algorithm for large-scale orienteering problems.

Paper link: https://arxiv.org/pdf/2011.02743.pdf

RG homepage: https://cw.fel.cvut.cz/wiki/courses/xp33rg2/start

Video call link: https://meet.google.com/jyu-vfim-kbc

Abstract:
The orienteering problem is a route optimization problem which consists in
finding a simple cycle
that maximizes the total collected profit subject to a maximum distance
limitation. In the last few
decades, the occurrence of this problem in real-life applications has boosted
the development of
many heuristic algorithms to solve it. However, during the same period, not
much
research has been
devoted to the field of exact algorithms for the orienteering problem. The aim
of this work is to
develop an exact method which is able to obtain optimality certification in a
wider set of instances
than with previous methods, or to improve the lower and upper bounds in its
disability.
We propose a revisited version of the branch-and-cut algorithm for the
orienteering problem which
includes new contributions in the separation algorithms of inequalities
stemming
from the cycle
problem, in the separation loop, in the variables pricing, and in the
calculation of the lower and
upper bounds of the problem. Our proposal is compared to three state-of-the-art
algorithms on 258
benchmark instances with up to 7397 nodes. The computational experiments show
the relevance of the
designed components where 18 new optima, 76 new best-known solutions and 85 new
upper-bound
values were obtained.