In this paper, we handle the problem of picking and delivering patients among the distinct units of a hospital. This problem is found in hospitals with several (specialized) units covering a large area, and it emerges from a real situation faced by a hospital in northern Italy. Patient transportation requests arrive dynamically during the day, and the hospital transportation department must service them all using capacitated and homogeneous vehicles. Each request is associated with a patient urgency level (weight) and a time window. The objective is to design vehicle routes to serve all requests and minimize the total weighted tardiness. To solve the problem, we propose a re-optimization heuristic based on two policies that mimic the patients’ and hospital’s decision-making processes. We then improve the solutions obtained with the policies using a tabu search. Computational results show that we can obtain high-quality solutions using the tabu search compared with the policies and a simulated annealing-based heuristic from the literature.

A Geração de Colunas (GC) é uma técnica para resolver Programas Lineares com um número muito grande de variáveis. Em vez de avaliar explicitamente custos reduzidos, as variáveis são geradas dinamicamente resolvendo problemas auxiliares de otimização conhecidos como subproblemas de pricing. A GC é uma das principais técnicas de otimização, sendo também eficaz em programação inteira, em algoritmos como Branch-and-Price e Branch-Cut-and-Price. Foi aplicada com sucesso em muitos tipos de roteamento de veículos, corte e empacotamento, planejamento de companhias aéreas, programação de horários, escalonamento de tripulações, coloração de grafos, clustering, dimensionamento de lotes e programação de máquinas, entre outros problemas. A palestra fornece uma visão geral da GC. A questão central explorada é - em que circunstâncias os algoritmos baseados em GC têm o potencial de superar outros métodos existentes? A discussão baseia-se em material do recente livro “Optimizing with Column Generation - advanced Branch-Cut-and-Price Algorithms (Part I)” disponível em https://optimizingwithcolumngeneration.github.io/.

Given a finite non-decreasing sequence d = (d₁, …, dₙ) of natural numbers, the Graph Realization problem asks whether d is a graphic sequence, i.e., there exists a labeled simple graph such that (d₁, …, dₙ) is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence d = (d₁, …, dₙ) of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints 𝒞 composed of pairs (Sⱼ, ℓⱼ) where Sⱼ ⊆ {v₁, …, vₙ}, and ℓⱼ is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set V = {v₁, …, vₙ} such that vᵢ has degree dᵢ and ∂(Sⱼ) is an edge cut of size ℓⱼ, for each (Sⱼ, ℓⱼ) ∈ 𝒞. We show that such a problem is polynomial-time solvable whenever each Sⱼ has size at most three. Conversely, assuming P ≠ NP, we prove that it cannot be solved in polynomial time when 𝒞 contains pairs with sets of size four, and our hardness result holds even assuming that each dᵢ of d equals 1.

Efficient operating theatre scheduling is essential for optimising hospital resources and ensuring organized sessions of medical procedures. This process involves scheduling time blocks for each operating theatre over a planning period and allocating them to medical specialities, while considering constraints such as medical team availability and theatre compatibility. In this work, we model operating theatre scheduling as an optimization problem and apply Mixed Integer Linear Programming (MILP) techniques to improve theatre utilisation and enable medical teams to operate more patients. Our case study focuses on the University of Campinas’ Clinical Hospital, a regional high-complexity centre of excellence that serves a population of around 5 million people. Additional challenges include transplant surgeries, priority surgeries and scarcity of anaesthetists. To address these complexities, we develop a hierarchical multi-objective optimisation model that incorporates packing and knapsack-based constraints and can be solved efficient with an open-source MILP solver. This study includes a pilot implementation of the model within the hospital setting for validation and refinement. Preliminary results indicate that the model is able to not only replicate the schedules produced manually by a highly experienced staff member, but also improve the utilisation of the surgical centre with respect to the current practice.

Apresentaremos uma abordagem de otimização para a construção de um dos mais importantes algoritmos de tomada de decisão. O seminário discutirá a transição de métodos heurísticos para modelos de otimização que priorizam não apenas a acurácia, mas também a interpretabilidade e a justiça, através de métricas como altura da árvore e “sparsity”. Serão exploradas técnicas de Programação Linear Inteira (PLI) e, em especial, discutiremos o resultado de Aghaei et al. (2024) que propõe uma nova e “mais forte” formulação para o problema.

O Problema Freeze-Tag Angular (AFTP) trata da distribuição de dados de missão em um enxame de satélites. Nesse cenário, os satélites não podem ser alcançados simultaneamente por meio de uma única transmissão; em vez disso, são necessárias antenas direcionais altamente focadas. Como consequência, um satélite só pode transmitir quando sua antena está orientada em direção ao receptor. Esse alinhamento pode exigir a reorientação da antena, o que acarreta um custo de tempo proporcional ao ângulo de rotação. O objetivo é minimizar o makespan, isto é, o tempo total de distribuição. Sabe-se que aproximar o AFTP no plano com fator melhor que 5/3 é um problema NP-difícil. Conseguimos superamos esse limite introduzindo dois novos parâmetros - A menor mudança de orientação necessária para a antena de um satélite, a partir de sua posição inicial, para alinhar-se com outro satélite; A energia total (ângulo de rotação). Essa parametrização nos permite projetar um esquema de aproximação parametrizado que executa em tempo XP. Além disso, nossa abordagem se estende à variante do AFTP que busca minimizar a energia total em vez do makespan.