Arc flow models with a pseudo-polynomial size usually provide strong relaxations, and have been successfully used to solve hard optimization problems in several domains, such as cutting, packing, scheduling, and routing. The relation between the underlying network and Dynamic Programming (DP) allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. In this talk, we address two generalizations of the classical bin packing problem: the temporal bin packing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on homogeneous servers of limited capacity. While TBPP is exclusively concerned with minimizing the number of servers in use, TBPP-FU additionally takes into account the switch-on processes required for their operation. In both cases, challenging integer optimization problems are obtained, which can differ significantly from each other despite the seemingly only marginal variation of the problems. We present a solution approach for both problems based on combinatorial arc flow models. Previous scientific contributions in this direction failed because of the exponential number of the necessary DP states and transitions. Our approach does not change the theoretical exponentiality itself, but it can make it controllable by clever construction of the network. This leads to the fact that for the first time all classical benchmark instances (and even larger ones) for the two problems can be solved -- in times that significantly improve those of the previous approaches.
Diariamente resolvemos problemas de roteamento e alocação nas nossas tarefas quotidianas. O mesmo acontece com instituições que, muitas vezes, sem saber da complexidade dos problemas, oferecem soluções distantes da otimalidade, sem saber que resolver tais problemas demandam conhecimento específico. Esta situação em geral só é percebida quando tais problemas já não são mais pequenos, e soluções não automatizadas são insatisfatórias. Nesta palestra descreve-se três casos reais de problemas que envolvem roteamento e alocação que estão sendo trabalhados em conjunto com alunos de pós-graduação e instituições de Porto Alegre. Um problema se refere ao roteamento de veículos para a entrega de produtos por uma empresa. Outro sobre a alocação de médicos plantonistas no Hospital de Clínicas de Porto Alegre. O terceiro problema trata da logística do atendimento médico domiciliar, incluindo alocação e roteamento, unindo conhecimento dos dois primeiros problemas. Na palestra detalhar-se-á, além das aplicações e as técnicas usadas para resolvê-las, o caminho trilhado para que houvesse produção científica e tecnológica.
In this talk, we present two frameworks based on the iterated local search (ILS) metaheuristic for solving classes of combinatorial optimization problems. The first framework consists of a combination of ILS and the randomized variable neighborhood descent (RVND) procedure, whereas the second one is a matheuristic approach that integrates ILS, RVND and a mathematical programming-based procedure. We consider classes of problems that can be represented using a single sequence of elements (e.g., variants of the traveling salesman problem, single machine scheduling problems), multiple sequences of elements (e.g., vehicle routing problems, parallel machine scheduling problems), and multiple sets of elements (e.g., clustering problems). Moreover, we provide guidelines on how to efficiently perform move evaluation and feasibility checking during local search, as well as efficient mechanisms to improve computational performance.